/usr/bin/java -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/AutomizerCInline.xml -s ../../../trunk/examples/settings/automizer/BvToInt/svcomp-Reach-64bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/recursive/gcd02.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-a10ec3b [2022-01-10 01:01:03,890 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-01-10 01:01:03,892 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-01-10 01:01:03,949 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-01-10 01:01:03,951 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-01-10 01:01:03,952 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-01-10 01:01:03,953 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-01-10 01:01:03,955 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-01-10 01:01:03,958 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-01-10 01:01:03,959 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-01-10 01:01:03,960 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-01-10 01:01:03,960 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-01-10 01:01:03,961 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-01-10 01:01:03,961 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-01-10 01:01:03,962 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-01-10 01:01:03,963 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-01-10 01:01:03,964 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-01-10 01:01:03,965 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-01-10 01:01:03,966 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-01-10 01:01:03,968 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-01-10 01:01:03,969 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-01-10 01:01:03,976 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-01-10 01:01:03,978 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-01-10 01:01:03,980 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-01-10 01:01:03,984 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-01-10 01:01:03,984 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-01-10 01:01:03,985 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-01-10 01:01:03,985 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-01-10 01:01:03,986 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-01-10 01:01:03,986 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-01-10 01:01:03,986 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-01-10 01:01:03,987 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-01-10 01:01:03,988 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-01-10 01:01:03,988 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-01-10 01:01:03,989 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-01-10 01:01:03,989 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-01-10 01:01:03,990 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-01-10 01:01:03,994 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-01-10 01:01:03,995 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-01-10 01:01:03,998 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-01-10 01:01:03,998 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-01-10 01:01:04,001 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/BvToInt/svcomp-Reach-64bit-Automizer_Default.epf [2022-01-10 01:01:04,033 INFO L113 SettingsManager]: Loading preferences was successful [2022-01-10 01:01:04,033 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-01-10 01:01:04,034 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-01-10 01:01:04,034 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-01-10 01:01:04,035 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-01-10 01:01:04,035 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-01-10 01:01:04,035 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-01-10 01:01:04,035 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-01-10 01:01:04,036 INFO L138 SettingsManager]: * Use SBE=true [2022-01-10 01:01:04,036 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-01-10 01:01:04,036 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-01-10 01:01:04,037 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-01-10 01:01:04,037 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-01-10 01:01:04,037 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-01-10 01:01:04,037 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-01-10 01:01:04,037 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2022-01-10 01:01:04,037 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-01-10 01:01:04,037 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-01-10 01:01:04,037 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-01-10 01:01:04,038 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-01-10 01:01:04,038 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-01-10 01:01:04,038 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-01-10 01:01:04,038 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-01-10 01:01:04,038 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-01-10 01:01:04,039 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-01-10 01:01:04,039 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-01-10 01:01:04,039 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-01-10 01:01:04,040 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2022-01-10 01:01:04,040 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-01-10 01:01:04,040 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-01-10 01:01:04,040 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode 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-01-10 01:01:04,248 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-01-10 01:01:04,270 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-01-10 01:01:04,273 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-01-10 01:01:04,274 INFO L271 PluginConnector]: Initializing CDTParser... [2022-01-10 01:01:04,275 INFO L275 PluginConnector]: CDTParser initialized [2022-01-10 01:01:04,276 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/recursive/gcd02.c [2022-01-10 01:01:04,332 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/546946bf1/2890cde731114c4fb388bae24e5b6230/FLAG68c138943 [2022-01-10 01:01:04,740 INFO L306 CDTParser]: Found 1 translation units. [2022-01-10 01:01:04,740 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/recursive/gcd02.c [2022-01-10 01:01:04,749 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/546946bf1/2890cde731114c4fb388bae24e5b6230/FLAG68c138943 [2022-01-10 01:01:04,763 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/546946bf1/2890cde731114c4fb388bae24e5b6230 [2022-01-10 01:01:04,765 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-01-10 01:01:04,766 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-01-10 01:01:04,769 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-01-10 01:01:04,770 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-01-10 01:01:04,772 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-01-10 01:01:04,773 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:04,774 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2a7b09d5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04, skipping insertion in model container [2022-01-10 01:01:04,774 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:04,779 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-01-10 01:01:04,792 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-01-10 01:01:04,922 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/recursive/gcd02.c[623,636] [2022-01-10 01:01:04,931 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/recursive/gcd02.c[1283,1296] [2022-01-10 01:01:04,932 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-01-10 01:01:04,937 INFO L203 MainTranslator]: Completed pre-run [2022-01-10 01:01:04,949 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/recursive/gcd02.c[623,636] [2022-01-10 01:01:04,955 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/recursive/gcd02.c[1283,1296] [2022-01-10 01:01:04,956 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-01-10 01:01:04,965 INFO L208 MainTranslator]: Completed translation [2022-01-10 01:01:04,965 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04 WrapperNode [2022-01-10 01:01:04,965 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-01-10 01:01:04,966 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-01-10 01:01:04,966 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-01-10 01:01:04,967 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-01-10 01:01:04,973 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:04,979 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:04,997 INFO L137 Inliner]: procedures = 14, calls = 12, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 37 [2022-01-10 01:01:04,998 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-01-10 01:01:04,998 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-01-10 01:01:04,998 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-01-10 01:01:04,998 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-01-10 01:01:05,005 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:05,005 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:05,006 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:05,006 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:05,009 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:05,010 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:05,011 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:05,012 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-01-10 01:01:05,013 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-01-10 01:01:05,013 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-01-10 01:01:05,013 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-01-10 01:01:05,014 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04" (1/1) ... [2022-01-10 01:01:05,029 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-01-10 01:01:05,037 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:05,046 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-01-10 01:01:05,054 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-01-10 01:01:05,076 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-01-10 01:01:05,077 INFO L130 BoogieDeclarations]: Found specification of procedure gcd [2022-01-10 01:01:05,077 INFO L138 BoogieDeclarations]: Found implementation of procedure gcd [2022-01-10 01:01:05,077 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-01-10 01:01:05,077 INFO L130 BoogieDeclarations]: Found specification of procedure divides [2022-01-10 01:01:05,077 INFO L138 BoogieDeclarations]: Found implementation of procedure divides [2022-01-10 01:01:05,077 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-01-10 01:01:05,077 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-01-10 01:01:05,119 INFO L234 CfgBuilder]: Building ICFG [2022-01-10 01:01:05,121 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-01-10 01:01:05,228 INFO L275 CfgBuilder]: Performing block encoding [2022-01-10 01:01:05,234 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-01-10 01:01:05,234 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2022-01-10 01:01:05,236 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 01:01:05 BoogieIcfgContainer [2022-01-10 01:01:05,236 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-01-10 01:01:05,237 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-01-10 01:01:05,238 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-01-10 01:01:05,240 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-01-10 01:01:05,241 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 10.01 01:01:04" (1/3) ... [2022-01-10 01:01:05,241 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@29d8187a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.01 01:01:05, skipping insertion in model container [2022-01-10 01:01:05,241 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.01 01:01:04" (2/3) ... [2022-01-10 01:01:05,242 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@29d8187a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.01 01:01:05, skipping insertion in model container [2022-01-10 01:01:05,242 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.01 01:01:05" (3/3) ... [2022-01-10 01:01:05,243 INFO L111 eAbstractionObserver]: Analyzing ICFG gcd02.c [2022-01-10 01:01:05,247 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-01-10 01:01:05,247 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 2 error locations. [2022-01-10 01:01:05,298 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-01-10 01:01:05,310 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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, mLoopAccelerationTechnique=FAST_UPR [2022-01-10 01:01:05,310 INFO L340 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2022-01-10 01:01:05,328 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 24 states have (on average 1.4583333333333333) internal successors, (35), 26 states have internal predecessors, (35), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-01-10 01:01:05,341 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2022-01-10 01:01:05,344 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:05,345 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:05,345 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting gcdErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:05,350 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:05,350 INFO L85 PathProgramCache]: Analyzing trace with hash 1041004109, now seen corresponding path program 1 times [2022-01-10 01:01:05,360 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:05,360 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1766162915] [2022-01-10 01:01:05,361 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:05,361 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:05,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:05,639 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-10 01:01:05,640 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:05,640 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1766162915] [2022-01-10 01:01:05,641 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1766162915] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 01:01:05,641 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 01:01:05,641 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-01-10 01:01:05,642 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [829354566] [2022-01-10 01:01:05,643 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 01:01:05,646 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-01-10 01:01:05,646 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:05,666 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-01-10 01:01:05,667 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2022-01-10 01:01:05,669 INFO L87 Difference]: Start difference. First operand has 34 states, 24 states have (on average 1.4583333333333333) internal successors, (35), 26 states have internal predecessors, (35), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-01-10 01:01:05,761 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:05,761 INFO L93 Difference]: Finished difference Result 78 states and 103 transitions. [2022-01-10 01:01:05,763 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-01-10 01:01:05,764 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2022-01-10 01:01:05,764 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:05,775 INFO L225 Difference]: With dead ends: 78 [2022-01-10 01:01:05,776 INFO L226 Difference]: Without dead ends: 41 [2022-01-10 01:01:05,780 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2022-01-10 01:01:05,785 INFO L933 BasicCegarLoop]: 40 mSDtfsCounter, 36 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:05,787 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [40 Valid, 154 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-10 01:01:05,802 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-01-10 01:01:05,820 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-01-10 01:01:05,821 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 29 states have (on average 1.2413793103448276) internal successors, (36), 30 states have internal predecessors, (36), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-01-10 01:01:05,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 50 transitions. [2022-01-10 01:01:05,824 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 50 transitions. Word has length 9 [2022-01-10 01:01:05,824 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:05,824 INFO L470 AbstractCegarLoop]: Abstraction has 41 states and 50 transitions. [2022-01-10 01:01:05,825 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-01-10 01:01:05,825 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 50 transitions. [2022-01-10 01:01:05,826 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-01-10 01:01:05,826 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:05,826 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:05,826 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-01-10 01:01:05,826 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting gcdErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:05,827 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:05,827 INFO L85 PathProgramCache]: Analyzing trace with hash -1602001293, now seen corresponding path program 1 times [2022-01-10 01:01:05,827 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:05,828 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1961093104] [2022-01-10 01:01:05,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:05,828 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:05,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:05,897 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-10 01:01:05,898 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:05,898 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1961093104] [2022-01-10 01:01:05,898 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1961093104] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 01:01:05,898 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 01:01:05,898 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-01-10 01:01:05,899 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [923744735] [2022-01-10 01:01:05,899 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 01:01:05,900 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-01-10 01:01:05,900 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:05,901 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-01-10 01:01:05,901 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2022-01-10 01:01:05,901 INFO L87 Difference]: Start difference. First operand 41 states and 50 transitions. Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-01-10 01:01:05,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:05,977 INFO L93 Difference]: Finished difference Result 59 states and 75 transitions. [2022-01-10 01:01:05,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-01-10 01:01:05,978 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2022-01-10 01:01:05,978 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:05,980 INFO L225 Difference]: With dead ends: 59 [2022-01-10 01:01:05,981 INFO L226 Difference]: Without dead ends: 57 [2022-01-10 01:01:05,981 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2022-01-10 01:01:05,982 INFO L933 BasicCegarLoop]: 42 mSDtfsCounter, 18 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:05,983 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [20 Valid, 129 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-10 01:01:05,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2022-01-10 01:01:06,004 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 51. [2022-01-10 01:01:06,005 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 36 states have (on average 1.25) internal successors, (45), 37 states have internal predecessors, (45), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-01-10 01:01:06,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 63 transitions. [2022-01-10 01:01:06,010 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 63 transitions. Word has length 14 [2022-01-10 01:01:06,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:06,010 INFO L470 AbstractCegarLoop]: Abstraction has 51 states and 63 transitions. [2022-01-10 01:01:06,010 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-01-10 01:01:06,010 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 63 transitions. [2022-01-10 01:01:06,011 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-01-10 01:01:06,011 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:06,011 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:06,011 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-01-10 01:01:06,012 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting gcdErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:06,012 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:06,012 INFO L85 PathProgramCache]: Analyzing trace with hash -1599171148, now seen corresponding path program 1 times [2022-01-10 01:01:06,012 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:06,013 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1423897581] [2022-01-10 01:01:06,013 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:06,013 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:06,029 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,095 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-10 01:01:06,096 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:06,096 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1423897581] [2022-01-10 01:01:06,096 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1423897581] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 01:01:06,096 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 01:01:06,097 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-01-10 01:01:06,097 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1981945304] [2022-01-10 01:01:06,097 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 01:01:06,097 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-01-10 01:01:06,098 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:06,098 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-01-10 01:01:06,098 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2022-01-10 01:01:06,099 INFO L87 Difference]: Start difference. First operand 51 states and 63 transitions. Second operand has 7 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-01-10 01:01:06,231 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:06,231 INFO L93 Difference]: Finished difference Result 63 states and 83 transitions. [2022-01-10 01:01:06,232 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-01-10 01:01:06,232 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2022-01-10 01:01:06,232 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:06,234 INFO L225 Difference]: With dead ends: 63 [2022-01-10 01:01:06,234 INFO L226 Difference]: Without dead ends: 61 [2022-01-10 01:01:06,234 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=45, Invalid=65, Unknown=0, NotChecked=0, Total=110 [2022-01-10 01:01:06,235 INFO L933 BasicCegarLoop]: 46 mSDtfsCounter, 23 mSDsluCounter, 116 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 162 SdHoareTripleChecker+Invalid, 67 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:06,236 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 162 Invalid, 67 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 01:01:06,237 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2022-01-10 01:01:06,247 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 49. [2022-01-10 01:01:06,248 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 35 states have (on average 1.2285714285714286) internal successors, (43), 35 states have internal predecessors, (43), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-01-10 01:01:06,249 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 61 transitions. [2022-01-10 01:01:06,249 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 61 transitions. Word has length 14 [2022-01-10 01:01:06,249 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:06,250 INFO L470 AbstractCegarLoop]: Abstraction has 49 states and 61 transitions. [2022-01-10 01:01:06,250 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-01-10 01:01:06,250 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 61 transitions. [2022-01-10 01:01:06,251 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-01-10 01:01:06,251 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:06,252 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:06,252 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-01-10 01:01:06,252 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:06,253 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:06,253 INFO L85 PathProgramCache]: Analyzing trace with hash -2110562560, now seen corresponding path program 1 times [2022-01-10 01:01:06,253 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:06,253 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2024144974] [2022-01-10 01:01:06,253 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:06,254 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:06,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,303 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:06,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,324 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-01-10 01:01:06,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,342 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-10 01:01:06,342 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:06,343 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2024144974] [2022-01-10 01:01:06,343 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2024144974] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 01:01:06,343 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 01:01:06,343 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-01-10 01:01:06,343 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1764301991] [2022-01-10 01:01:06,344 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 01:01:06,344 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-01-10 01:01:06,344 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:06,345 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-01-10 01:01:06,345 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-01-10 01:01:06,345 INFO L87 Difference]: Start difference. First operand 49 states and 61 transitions. Second operand has 4 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 01:01:06,371 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:06,372 INFO L93 Difference]: Finished difference Result 55 states and 67 transitions. [2022-01-10 01:01:06,372 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-01-10 01:01:06,372 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 20 [2022-01-10 01:01:06,373 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:06,374 INFO L225 Difference]: With dead ends: 55 [2022-01-10 01:01:06,374 INFO L226 Difference]: Without dead ends: 51 [2022-01-10 01:01:06,374 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-01-10 01:01:06,384 INFO L933 BasicCegarLoop]: 34 mSDtfsCounter, 0 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:06,384 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 97 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-10 01:01:06,385 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-01-10 01:01:06,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2022-01-10 01:01:06,399 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 37 states have internal predecessors, (44), 9 states have call successors, (9), 4 states have call predecessors, (9), 5 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2022-01-10 01:01:06,400 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 63 transitions. [2022-01-10 01:01:06,401 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 63 transitions. Word has length 20 [2022-01-10 01:01:06,401 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:06,401 INFO L470 AbstractCegarLoop]: Abstraction has 51 states and 63 transitions. [2022-01-10 01:01:06,401 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-10 01:01:06,408 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 63 transitions. [2022-01-10 01:01:06,409 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-01-10 01:01:06,409 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:06,410 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:06,410 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-01-10 01:01:06,410 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:06,411 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:06,411 INFO L85 PathProgramCache]: Analyzing trace with hash -291106652, now seen corresponding path program 1 times [2022-01-10 01:01:06,411 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:06,411 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1325808115] [2022-01-10 01:01:06,411 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:06,412 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:06,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,458 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:06,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,484 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-01-10 01:01:06,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,520 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-10 01:01:06,521 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:06,521 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1325808115] [2022-01-10 01:01:06,521 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1325808115] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 01:01:06,521 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 01:01:06,521 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-01-10 01:01:06,522 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1585065987] [2022-01-10 01:01:06,522 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 01:01:06,522 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-01-10 01:01:06,522 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:06,523 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-01-10 01:01:06,523 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2022-01-10 01:01:06,523 INFO L87 Difference]: Start difference. First operand 51 states and 63 transitions. Second operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-01-10 01:01:06,674 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:06,675 INFO L93 Difference]: Finished difference Result 69 states and 86 transitions. [2022-01-10 01:01:06,675 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-01-10 01:01:06,676 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2022-01-10 01:01:06,677 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:06,684 INFO L225 Difference]: With dead ends: 69 [2022-01-10 01:01:06,685 INFO L226 Difference]: Without dead ends: 65 [2022-01-10 01:01:06,686 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-01-10 01:01:06,692 INFO L933 BasicCegarLoop]: 21 mSDtfsCounter, 16 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 142 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 142 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 142 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:06,692 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 106 Invalid, 142 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 142 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 01:01:06,693 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2022-01-10 01:01:06,703 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 57. [2022-01-10 01:01:06,710 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 39 states have (on average 1.205128205128205) internal successors, (47), 42 states have internal predecessors, (47), 10 states have call successors, (10), 4 states have call predecessors, (10), 7 states have return successors, (14), 10 states have call predecessors, (14), 10 states have call successors, (14) [2022-01-10 01:01:06,715 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 71 transitions. [2022-01-10 01:01:06,716 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 71 transitions. Word has length 21 [2022-01-10 01:01:06,718 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:06,719 INFO L470 AbstractCegarLoop]: Abstraction has 57 states and 71 transitions. [2022-01-10 01:01:06,722 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-01-10 01:01:06,722 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 71 transitions. [2022-01-10 01:01:06,723 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-01-10 01:01:06,723 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:06,723 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:06,723 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2022-01-10 01:01:06,724 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:06,724 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:06,724 INFO L85 PathProgramCache]: Analyzing trace with hash -1709846180, now seen corresponding path program 1 times [2022-01-10 01:01:06,724 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:06,724 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1384035113] [2022-01-10 01:01:06,724 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:06,725 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:06,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,787 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:06,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,795 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-01-10 01:01:06,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,838 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:06,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,862 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 01:01:06,862 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:06,863 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1384035113] [2022-01-10 01:01:06,863 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1384035113] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 01:01:06,863 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 01:01:06,863 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-01-10 01:01:06,863 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1920952310] [2022-01-10 01:01:06,863 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 01:01:06,864 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-01-10 01:01:06,864 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:06,864 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-01-10 01:01:06,864 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-01-10 01:01:06,864 INFO L87 Difference]: Start difference. First operand 57 states and 71 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 1 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2022-01-10 01:01:06,886 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:06,886 INFO L93 Difference]: Finished difference Result 64 states and 79 transitions. [2022-01-10 01:01:06,886 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-01-10 01:01:06,887 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 1 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) Word has length 27 [2022-01-10 01:01:06,887 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:06,888 INFO L225 Difference]: With dead ends: 64 [2022-01-10 01:01:06,888 INFO L226 Difference]: Without dead ends: 55 [2022-01-10 01:01:06,888 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-01-10 01:01:06,889 INFO L933 BasicCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:06,889 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 128 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-10 01:01:06,890 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-01-10 01:01:06,903 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-01-10 01:01:06,903 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 10 states have call successors, (10), 4 states have call predecessors, (10), 6 states have return successors, (13), 10 states have call predecessors, (13), 10 states have call successors, (13) [2022-01-10 01:01:06,904 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-01-10 01:01:06,904 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 27 [2022-01-10 01:01:06,910 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:06,910 INFO L470 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-01-10 01:01:06,911 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 1 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2022-01-10 01:01:06,911 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-01-10 01:01:06,912 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-01-10 01:01:06,912 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:06,912 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:06,912 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2022-01-10 01:01:06,913 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:06,913 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:06,913 INFO L85 PathProgramCache]: Analyzing trace with hash -1148028586, now seen corresponding path program 1 times [2022-01-10 01:01:06,913 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:06,913 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1386535125] [2022-01-10 01:01:06,913 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:06,913 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:06,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:06,967 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:06,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:07,000 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-01-10 01:01:07,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:07,067 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:07,074 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:07,115 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-01-10 01:01:07,116 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:07,116 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1386535125] [2022-01-10 01:01:07,116 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1386535125] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:07,116 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [391954347] [2022-01-10 01:01:07,116 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:07,116 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:07,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:07,119 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-01-10 01:01:07,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-01-10 01:01:07,175 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:07,184 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 23 conjunts are in the unsatisfiable core [2022-01-10 01:01:07,188 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:07,380 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-01-10 01:01:07,380 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:07,633 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-01-10 01:01:07,634 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [391954347] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:07,634 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:07,634 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10, 10] total 14 [2022-01-10 01:01:07,634 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1749983021] [2022-01-10 01:01:07,634 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:07,635 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-01-10 01:01:07,636 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:07,636 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-01-10 01:01:07,637 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2022-01-10 01:01:07,637 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 14 states, 12 states have (on average 2.5) internal successors, (30), 13 states have internal predecessors, (30), 5 states have call successors, (5), 1 states have call predecessors, (5), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) [2022-01-10 01:01:07,818 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:07,818 INFO L93 Difference]: Finished difference Result 63 states and 79 transitions. [2022-01-10 01:01:07,818 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-01-10 01:01:07,819 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.5) internal successors, (30), 13 states have internal predecessors, (30), 5 states have call successors, (5), 1 states have call predecessors, (5), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) Word has length 28 [2022-01-10 01:01:07,819 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:07,821 INFO L225 Difference]: With dead ends: 63 [2022-01-10 01:01:07,822 INFO L226 Difference]: Without dead ends: 55 [2022-01-10 01:01:07,823 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 52 SyntacticMatches, 4 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=79, Invalid=263, Unknown=0, NotChecked=0, Total=342 [2022-01-10 01:01:07,826 INFO L933 BasicCegarLoop]: 21 mSDtfsCounter, 18 mSDsluCounter, 124 mSDsCounter, 0 mSdLazyCounter, 181 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 185 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 181 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:07,826 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 145 Invalid, 185 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 181 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 01:01:07,829 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-01-10 01:01:07,842 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 49. [2022-01-10 01:01:07,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 35 states have internal predecessors, (41), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-01-10 01:01:07,843 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 59 transitions. [2022-01-10 01:01:07,843 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 59 transitions. Word has length 28 [2022-01-10 01:01:07,844 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:07,844 INFO L470 AbstractCegarLoop]: Abstraction has 49 states and 59 transitions. [2022-01-10 01:01:07,844 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.5) internal successors, (30), 13 states have internal predecessors, (30), 5 states have call successors, (5), 1 states have call predecessors, (5), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) [2022-01-10 01:01:07,844 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 59 transitions. [2022-01-10 01:01:07,845 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-01-10 01:01:07,845 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:07,845 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:07,864 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-01-10 01:01:08,045 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:08,046 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:08,046 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:08,047 INFO L85 PathProgramCache]: Analyzing trace with hash -729806600, now seen corresponding path program 1 times [2022-01-10 01:01:08,047 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:08,047 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1862341215] [2022-01-10 01:01:08,047 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:08,047 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:08,063 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:08,093 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:08,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:08,145 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:08,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:08,170 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2022-01-10 01:01:08,173 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:08,210 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-01-10 01:01:08,211 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:08,211 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1862341215] [2022-01-10 01:01:08,211 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1862341215] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:08,211 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [201722178] [2022-01-10 01:01:08,211 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:08,211 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:08,212 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:08,216 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-01-10 01:01:08,231 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-01-10 01:01:08,280 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:08,281 INFO L263 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 15 conjunts are in the unsatisfiable core [2022-01-10 01:01:08,283 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:08,427 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-01-10 01:01:08,428 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:08,725 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-01-10 01:01:08,725 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [201722178] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:08,725 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:08,725 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 20 [2022-01-10 01:01:08,726 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [241608744] [2022-01-10 01:01:08,726 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:08,726 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-01-10 01:01:08,726 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:08,727 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-01-10 01:01:08,727 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=324, Unknown=0, NotChecked=0, Total=380 [2022-01-10 01:01:08,727 INFO L87 Difference]: Start difference. First operand 49 states and 59 transitions. Second operand has 20 states, 18 states have (on average 2.2222222222222223) internal successors, (40), 16 states have internal predecessors, (40), 6 states have call successors, (6), 1 states have call predecessors, (6), 3 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) [2022-01-10 01:01:08,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:08,908 INFO L93 Difference]: Finished difference Result 74 states and 93 transitions. [2022-01-10 01:01:08,908 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-01-10 01:01:08,908 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.2222222222222223) internal successors, (40), 16 states have internal predecessors, (40), 6 states have call successors, (6), 1 states have call predecessors, (6), 3 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) Word has length 29 [2022-01-10 01:01:08,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:08,909 INFO L225 Difference]: With dead ends: 74 [2022-01-10 01:01:08,910 INFO L226 Difference]: Without dead ends: 70 [2022-01-10 01:01:08,910 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 50 SyntacticMatches, 3 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=92, Invalid=460, Unknown=0, NotChecked=0, Total=552 [2022-01-10 01:01:08,911 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 32 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 206 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 212 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 206 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:08,911 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 185 Invalid, 212 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 206 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 01:01:08,912 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2022-01-10 01:01:08,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 59. [2022-01-10 01:01:08,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 41 states have (on average 1.146341463414634) internal successors, (47), 42 states have internal predecessors, (47), 10 states have call successors, (10), 4 states have call predecessors, (10), 7 states have return successors, (16), 12 states have call predecessors, (16), 10 states have call successors, (16) [2022-01-10 01:01:08,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 73 transitions. [2022-01-10 01:01:08,920 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 73 transitions. Word has length 29 [2022-01-10 01:01:08,920 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:08,921 INFO L470 AbstractCegarLoop]: Abstraction has 59 states and 73 transitions. [2022-01-10 01:01:08,921 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.2222222222222223) internal successors, (40), 16 states have internal predecessors, (40), 6 states have call successors, (6), 1 states have call predecessors, (6), 3 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) [2022-01-10 01:01:08,921 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 73 transitions. [2022-01-10 01:01:08,922 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-01-10 01:01:08,922 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:08,922 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:08,940 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-01-10 01:01:09,127 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2022-01-10 01:01:09,128 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:09,128 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:09,128 INFO L85 PathProgramCache]: Analyzing trace with hash -1241581992, now seen corresponding path program 1 times [2022-01-10 01:01:09,128 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:09,128 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1515307038] [2022-01-10 01:01:09,129 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:09,129 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:09,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:09,153 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:09,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:09,179 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:09,182 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:09,188 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2022-01-10 01:01:09,198 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:09,222 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-01-10 01:01:09,222 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:09,222 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1515307038] [2022-01-10 01:01:09,222 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1515307038] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-10 01:01:09,222 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-10 01:01:09,222 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-01-10 01:01:09,222 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [188526585] [2022-01-10 01:01:09,222 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-10 01:01:09,223 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-01-10 01:01:09,223 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:09,223 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-01-10 01:01:09,223 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2022-01-10 01:01:09,224 INFO L87 Difference]: Start difference. First operand 59 states and 73 transitions. Second operand has 9 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-01-10 01:01:09,325 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:09,325 INFO L93 Difference]: Finished difference Result 80 states and 100 transitions. [2022-01-10 01:01:09,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-01-10 01:01:09,326 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 29 [2022-01-10 01:01:09,326 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:09,327 INFO L225 Difference]: With dead ends: 80 [2022-01-10 01:01:09,327 INFO L226 Difference]: Without dead ends: 76 [2022-01-10 01:01:09,327 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2022-01-10 01:01:09,329 INFO L933 BasicCegarLoop]: 21 mSDtfsCounter, 14 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 167 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 168 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 167 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:09,329 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [21 Valid, 122 Invalid, 168 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 167 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 01:01:09,331 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2022-01-10 01:01:09,350 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 63. [2022-01-10 01:01:09,350 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 44 states have (on average 1.1363636363636365) internal successors, (50), 44 states have internal predecessors, (50), 10 states have call successors, (10), 4 states have call predecessors, (10), 8 states have return successors, (19), 14 states have call predecessors, (19), 10 states have call successors, (19) [2022-01-10 01:01:09,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 79 transitions. [2022-01-10 01:01:09,351 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 79 transitions. Word has length 29 [2022-01-10 01:01:09,351 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:09,351 INFO L470 AbstractCegarLoop]: Abstraction has 63 states and 79 transitions. [2022-01-10 01:01:09,351 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-01-10 01:01:09,352 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 79 transitions. [2022-01-10 01:01:09,352 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-01-10 01:01:09,352 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:09,353 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:09,353 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2022-01-10 01:01:09,353 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:09,353 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:09,353 INFO L85 PathProgramCache]: Analyzing trace with hash 2029271682, now seen corresponding path program 1 times [2022-01-10 01:01:09,353 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:09,353 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1848904489] [2022-01-10 01:01:09,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:09,354 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:09,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:09,395 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:09,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:09,419 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:09,421 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:09,442 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2022-01-10 01:01:09,445 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:09,469 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:09,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:09,495 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 01:01:09,495 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:09,495 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1848904489] [2022-01-10 01:01:09,495 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1848904489] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:09,495 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1076241493] [2022-01-10 01:01:09,495 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:09,498 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:09,498 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:09,499 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-01-10 01:01:09,526 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-01-10 01:01:09,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:09,553 INFO L263 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 21 conjunts are in the unsatisfiable core [2022-01-10 01:01:09,557 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:09,752 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 01:01:09,752 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:10,256 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-01-10 01:01:10,256 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1076241493] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:10,256 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:10,256 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 13] total 20 [2022-01-10 01:01:10,256 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1931637834] [2022-01-10 01:01:10,257 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:10,257 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-01-10 01:01:10,257 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:10,258 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-01-10 01:01:10,258 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=324, Unknown=0, NotChecked=0, Total=380 [2022-01-10 01:01:10,258 INFO L87 Difference]: Start difference. First operand 63 states and 79 transitions. Second operand has 20 states, 19 states have (on average 2.6842105263157894) internal successors, (51), 18 states have internal predecessors, (51), 8 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (8), 4 states have call predecessors, (8), 8 states have call successors, (8) [2022-01-10 01:01:10,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:10,483 INFO L93 Difference]: Finished difference Result 89 states and 115 transitions. [2022-01-10 01:01:10,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-01-10 01:01:10,483 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 2.6842105263157894) internal successors, (51), 18 states have internal predecessors, (51), 8 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (8), 4 states have call predecessors, (8), 8 states have call successors, (8) Word has length 36 [2022-01-10 01:01:10,483 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:10,484 INFO L225 Difference]: With dead ends: 89 [2022-01-10 01:01:10,484 INFO L226 Difference]: Without dead ends: 85 [2022-01-10 01:01:10,485 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 58 SyntacticMatches, 11 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 94 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=98, Invalid=502, Unknown=0, NotChecked=0, Total=600 [2022-01-10 01:01:10,485 INFO L933 BasicCegarLoop]: 24 mSDtfsCounter, 48 mSDsluCounter, 187 mSDsCounter, 0 mSdLazyCounter, 266 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 211 SdHoareTripleChecker+Invalid, 291 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 266 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:10,485 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [58 Valid, 211 Invalid, 291 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 266 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-01-10 01:01:10,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2022-01-10 01:01:10,497 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 73. [2022-01-10 01:01:10,497 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 50 states have (on average 1.12) internal successors, (56), 51 states have internal predecessors, (56), 11 states have call successors, (11), 4 states have call predecessors, (11), 11 states have return successors, (27), 17 states have call predecessors, (27), 11 states have call successors, (27) [2022-01-10 01:01:10,498 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 94 transitions. [2022-01-10 01:01:10,499 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 94 transitions. Word has length 36 [2022-01-10 01:01:10,499 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:10,499 INFO L470 AbstractCegarLoop]: Abstraction has 73 states and 94 transitions. [2022-01-10 01:01:10,499 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 2.6842105263157894) internal successors, (51), 18 states have internal predecessors, (51), 8 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (8), 4 states have call predecessors, (8), 8 states have call successors, (8) [2022-01-10 01:01:10,499 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 94 transitions. [2022-01-10 01:01:10,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-01-10 01:01:10,502 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:10,503 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:10,529 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-01-10 01:01:10,723 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:10,724 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:10,724 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:10,724 INFO L85 PathProgramCache]: Analyzing trace with hash -122584798, now seen corresponding path program 1 times [2022-01-10 01:01:10,724 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:10,724 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1631835605] [2022-01-10 01:01:10,724 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:10,724 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:10,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:10,758 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:10,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:10,788 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:10,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:10,798 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2022-01-10 01:01:10,801 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:10,837 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:10,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:10,874 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-01-10 01:01:10,874 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:10,874 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1631835605] [2022-01-10 01:01:10,874 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1631835605] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:10,874 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [723970205] [2022-01-10 01:01:10,874 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:10,874 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:10,875 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:10,876 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-01-10 01:01:10,883 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-01-10 01:01:10,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:10,922 INFO L263 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 31 conjunts are in the unsatisfiable core [2022-01-10 01:01:10,924 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:11,045 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-01-10 01:01:11,046 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:11,315 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-01-10 01:01:11,316 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [723970205] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:11,316 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:11,316 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 11] total 15 [2022-01-10 01:01:11,316 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [975416819] [2022-01-10 01:01:11,316 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:11,317 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-01-10 01:01:11,317 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:11,318 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-01-10 01:01:11,318 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2022-01-10 01:01:11,318 INFO L87 Difference]: Start difference. First operand 73 states and 94 transitions. Second operand has 15 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 6 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) [2022-01-10 01:01:11,480 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:11,480 INFO L93 Difference]: Finished difference Result 84 states and 108 transitions. [2022-01-10 01:01:11,481 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-01-10 01:01:11,481 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 6 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) Word has length 36 [2022-01-10 01:01:11,481 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:11,482 INFO L225 Difference]: With dead ends: 84 [2022-01-10 01:01:11,482 INFO L226 Difference]: Without dead ends: 75 [2022-01-10 01:01:11,484 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 70 SyntacticMatches, 5 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=85, Invalid=335, Unknown=0, NotChecked=0, Total=420 [2022-01-10 01:01:11,485 INFO L933 BasicCegarLoop]: 22 mSDtfsCounter, 20 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 165 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 171 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 165 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:11,485 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 128 Invalid, 171 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 165 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 01:01:11,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2022-01-10 01:01:11,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 72. [2022-01-10 01:01:11,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 49 states have (on average 1.1224489795918366) internal successors, (55), 51 states have internal predecessors, (55), 11 states have call successors, (11), 4 states have call predecessors, (11), 11 states have return successors, (26), 16 states have call predecessors, (26), 11 states have call successors, (26) [2022-01-10 01:01:11,495 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 92 transitions. [2022-01-10 01:01:11,495 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 92 transitions. Word has length 36 [2022-01-10 01:01:11,495 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:11,497 INFO L470 AbstractCegarLoop]: Abstraction has 72 states and 92 transitions. [2022-01-10 01:01:11,498 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 6 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) [2022-01-10 01:01:11,498 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 92 transitions. [2022-01-10 01:01:11,498 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-01-10 01:01:11,498 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:11,499 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:11,523 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-01-10 01:01:11,699 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:11,699 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:11,700 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:11,700 INFO L85 PathProgramCache]: Analyzing trace with hash 1326914756, now seen corresponding path program 1 times [2022-01-10 01:01:11,700 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:11,700 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [492763429] [2022-01-10 01:01:11,700 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:11,700 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:11,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:11,732 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:11,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:11,768 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:11,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:11,812 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:11,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:11,864 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-01-10 01:01:11,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:11,894 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-01-10 01:01:11,895 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:11,895 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [492763429] [2022-01-10 01:01:11,895 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [492763429] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:11,895 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [3148529] [2022-01-10 01:01:11,895 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:11,895 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:11,895 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:11,897 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:11,898 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-01-10 01:01:11,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:11,942 INFO L263 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 22 conjunts are in the unsatisfiable core [2022-01-10 01:01:11,944 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:12,251 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 3 proven. 10 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-01-10 01:01:12,251 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:12,876 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-01-10 01:01:12,876 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [3148529] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:12,876 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:12,876 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 16, 16] total 39 [2022-01-10 01:01:12,879 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [401312026] [2022-01-10 01:01:12,879 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:12,880 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 39 states [2022-01-10 01:01:12,880 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:12,880 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2022-01-10 01:01:12,882 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=133, Invalid=1349, Unknown=0, NotChecked=0, Total=1482 [2022-01-10 01:01:12,882 INFO L87 Difference]: Start difference. First operand 72 states and 92 transitions. Second operand has 39 states, 32 states have (on average 1.9375) internal successors, (62), 31 states have internal predecessors, (62), 9 states have call successors, (9), 1 states have call predecessors, (9), 8 states have return successors, (12), 9 states have call predecessors, (12), 9 states have call successors, (12) [2022-01-10 01:01:13,385 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:13,385 INFO L93 Difference]: Finished difference Result 121 states and 159 transitions. [2022-01-10 01:01:13,385 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-01-10 01:01:13,386 INFO L78 Accepts]: Start accepts. Automaton has has 39 states, 32 states have (on average 1.9375) internal successors, (62), 31 states have internal predecessors, (62), 9 states have call successors, (9), 1 states have call predecessors, (9), 8 states have return successors, (12), 9 states have call predecessors, (12), 9 states have call successors, (12) Word has length 37 [2022-01-10 01:01:13,386 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:13,387 INFO L225 Difference]: With dead ends: 121 [2022-01-10 01:01:13,387 INFO L226 Difference]: Without dead ends: 117 [2022-01-10 01:01:13,388 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 52 SyntacticMatches, 4 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 562 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=307, Invalid=2045, Unknown=0, NotChecked=0, Total=2352 [2022-01-10 01:01:13,388 INFO L933 BasicCegarLoop]: 25 mSDtfsCounter, 87 mSDsluCounter, 345 mSDsCounter, 0 mSdLazyCounter, 558 mSolverCounterSat, 89 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 91 SdHoareTripleChecker+Valid, 370 SdHoareTripleChecker+Invalid, 647 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 89 IncrementalHoareTripleChecker+Valid, 558 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:13,388 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [91 Valid, 370 Invalid, 647 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [89 Valid, 558 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-01-10 01:01:13,389 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2022-01-10 01:01:13,397 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 78. [2022-01-10 01:01:13,397 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 53 states have (on average 1.1132075471698113) internal successors, (59), 55 states have internal predecessors, (59), 11 states have call successors, (11), 4 states have call predecessors, (11), 13 states have return successors, (31), 18 states have call predecessors, (31), 11 states have call successors, (31) [2022-01-10 01:01:13,398 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 101 transitions. [2022-01-10 01:01:13,398 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 101 transitions. Word has length 37 [2022-01-10 01:01:13,398 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:13,398 INFO L470 AbstractCegarLoop]: Abstraction has 78 states and 101 transitions. [2022-01-10 01:01:13,398 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 39 states, 32 states have (on average 1.9375) internal successors, (62), 31 states have internal predecessors, (62), 9 states have call successors, (9), 1 states have call predecessors, (9), 8 states have return successors, (12), 9 states have call predecessors, (12), 9 states have call successors, (12) [2022-01-10 01:01:13,398 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 101 transitions. [2022-01-10 01:01:13,401 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-01-10 01:01:13,401 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:13,402 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:13,421 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-01-10 01:01:13,612 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-01-10 01:01:13,612 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:13,613 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:13,613 INFO L85 PathProgramCache]: Analyzing trace with hash -238590844, now seen corresponding path program 2 times [2022-01-10 01:01:13,613 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:13,613 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [989149186] [2022-01-10 01:01:13,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:13,613 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:13,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:13,634 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:13,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:13,656 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:13,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:13,679 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:13,681 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:13,693 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-01-10 01:01:13,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:13,716 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-01-10 01:01:13,717 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:13,717 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [989149186] [2022-01-10 01:01:13,717 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [989149186] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:13,717 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1326186733] [2022-01-10 01:01:13,717 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-01-10 01:01:13,717 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:13,717 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:13,720 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:13,730 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-01-10 01:01:13,772 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-01-10 01:01:13,773 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 01:01:13,773 INFO L263 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 20 conjunts are in the unsatisfiable core [2022-01-10 01:01:13,775 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:13,902 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-01-10 01:01:13,902 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:14,326 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 3 proven. 10 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-01-10 01:01:14,327 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1326186733] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:14,327 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:14,327 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13, 15] total 22 [2022-01-10 01:01:14,327 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [496019942] [2022-01-10 01:01:14,327 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:14,329 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-01-10 01:01:14,329 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:14,330 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-01-10 01:01:14,330 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=407, Unknown=0, NotChecked=0, Total=462 [2022-01-10 01:01:14,330 INFO L87 Difference]: Start difference. First operand 78 states and 101 transitions. Second operand has 22 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 17 states have internal predecessors, (46), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (9), 6 states have call predecessors, (9), 8 states have call successors, (9) [2022-01-10 01:01:14,656 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:14,657 INFO L93 Difference]: Finished difference Result 96 states and 128 transitions. [2022-01-10 01:01:14,657 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-01-10 01:01:14,657 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 17 states have internal predecessors, (46), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (9), 6 states have call predecessors, (9), 8 states have call successors, (9) Word has length 37 [2022-01-10 01:01:14,657 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:14,658 INFO L225 Difference]: With dead ends: 96 [2022-01-10 01:01:14,658 INFO L226 Difference]: Without dead ends: 92 [2022-01-10 01:01:14,659 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 67 SyntacticMatches, 4 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 108 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=168, Invalid=888, Unknown=0, NotChecked=0, Total=1056 [2022-01-10 01:01:14,659 INFO L933 BasicCegarLoop]: 19 mSDtfsCounter, 38 mSDsluCounter, 191 mSDsCounter, 0 mSdLazyCounter, 295 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 210 SdHoareTripleChecker+Invalid, 330 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 295 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:14,660 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 210 Invalid, 330 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 295 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-10 01:01:14,660 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-01-10 01:01:14,665 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 64. [2022-01-10 01:01:14,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 44 states have (on average 1.1363636363636365) internal successors, (50), 46 states have internal predecessors, (50), 10 states have call successors, (10), 4 states have call predecessors, (10), 9 states have return successors, (19), 13 states have call predecessors, (19), 10 states have call successors, (19) [2022-01-10 01:01:14,666 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 79 transitions. [2022-01-10 01:01:14,666 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 79 transitions. Word has length 37 [2022-01-10 01:01:14,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:14,666 INFO L470 AbstractCegarLoop]: Abstraction has 64 states and 79 transitions. [2022-01-10 01:01:14,666 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 17 states have internal predecessors, (46), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (9), 6 states have call predecessors, (9), 8 states have call successors, (9) [2022-01-10 01:01:14,667 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 79 transitions. [2022-01-10 01:01:14,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-01-10 01:01:14,667 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:14,667 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:14,690 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-01-10 01:01:14,887 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:14,888 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:14,888 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:14,888 INFO L85 PathProgramCache]: Analyzing trace with hash 861262790, now seen corresponding path program 2 times [2022-01-10 01:01:14,888 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:14,888 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [730904298] [2022-01-10 01:01:14,888 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:14,888 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:14,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:14,914 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:14,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:14,938 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:14,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:14,970 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:14,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:14,987 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-01-10 01:01:14,990 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:15,018 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:15,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:15,041 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:15,042 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:15,062 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 6 proven. 14 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-01-10 01:01:15,063 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:15,063 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [730904298] [2022-01-10 01:01:15,063 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [730904298] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:15,063 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [987014794] [2022-01-10 01:01:15,063 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-01-10 01:01:15,063 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:15,063 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:15,064 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:15,071 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-01-10 01:01:15,123 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-01-10 01:01:15,124 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 01:01:15,125 INFO L263 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 31 conjunts are in the unsatisfiable core [2022-01-10 01:01:15,134 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:15,443 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 6 proven. 14 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-01-10 01:01:15,444 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:16,455 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 29 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-01-10 01:01:16,455 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [987014794] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:16,455 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:16,455 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 18] total 27 [2022-01-10 01:01:16,455 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [197683856] [2022-01-10 01:01:16,455 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:16,456 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2022-01-10 01:01:16,456 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:16,456 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2022-01-10 01:01:16,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=625, Unknown=0, NotChecked=0, Total=702 [2022-01-10 01:01:16,457 INFO L87 Difference]: Start difference. First operand 64 states and 79 transitions. Second operand has 27 states, 26 states have (on average 2.6153846153846154) internal successors, (68), 23 states have internal predecessors, (68), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (14), 7 states have call predecessors, (14), 12 states have call successors, (14) [2022-01-10 01:01:16,820 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:16,820 INFO L93 Difference]: Finished difference Result 94 states and 121 transitions. [2022-01-10 01:01:16,820 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-01-10 01:01:16,821 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 26 states have (on average 2.6153846153846154) internal successors, (68), 23 states have internal predecessors, (68), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (14), 7 states have call predecessors, (14), 12 states have call successors, (14) Word has length 51 [2022-01-10 01:01:16,821 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:16,822 INFO L225 Difference]: With dead ends: 94 [2022-01-10 01:01:16,822 INFO L226 Difference]: Without dead ends: 90 [2022-01-10 01:01:16,822 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 83 SyntacticMatches, 16 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 209 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=154, Invalid=1036, Unknown=0, NotChecked=0, Total=1190 [2022-01-10 01:01:16,823 INFO L933 BasicCegarLoop]: 29 mSDtfsCounter, 43 mSDsluCounter, 355 mSDsCounter, 0 mSdLazyCounter, 491 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 384 SdHoareTripleChecker+Invalid, 511 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 491 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:16,823 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [53 Valid, 384 Invalid, 511 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 491 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-01-10 01:01:16,823 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2022-01-10 01:01:16,829 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 75. [2022-01-10 01:01:16,829 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 51 states have (on average 1.1176470588235294) internal successors, (57), 53 states have internal predecessors, (57), 11 states have call successors, (11), 4 states have call predecessors, (11), 12 states have return successors, (28), 17 states have call predecessors, (28), 11 states have call successors, (28) [2022-01-10 01:01:16,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 96 transitions. [2022-01-10 01:01:16,830 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 96 transitions. Word has length 51 [2022-01-10 01:01:16,830 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:16,830 INFO L470 AbstractCegarLoop]: Abstraction has 75 states and 96 transitions. [2022-01-10 01:01:16,831 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 26 states have (on average 2.6153846153846154) internal successors, (68), 23 states have internal predecessors, (68), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (14), 7 states have call predecessors, (14), 12 states have call successors, (14) [2022-01-10 01:01:16,831 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 96 transitions. [2022-01-10 01:01:16,832 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-01-10 01:01:16,832 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:16,832 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:16,859 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-01-10 01:01:17,045 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:17,045 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:17,046 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:17,046 INFO L85 PathProgramCache]: Analyzing trace with hash -124726374, now seen corresponding path program 3 times [2022-01-10 01:01:17,046 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:17,046 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [898489337] [2022-01-10 01:01:17,046 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:17,046 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:17,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:17,079 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:17,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:17,108 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:17,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:17,134 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2022-01-10 01:01:17,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:17,165 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:17,167 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:17,200 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:17,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:17,227 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-01-10 01:01:17,227 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:17,227 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [898489337] [2022-01-10 01:01:17,227 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [898489337] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:17,228 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2136599271] [2022-01-10 01:01:17,228 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-01-10 01:01:17,228 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:17,228 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:17,229 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:17,230 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-01-10 01:01:17,287 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-01-10 01:01:17,287 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 01:01:17,288 INFO L263 TraceCheckSpWp]: Trace formula consists of 141 conjuncts, 26 conjunts are in the unsatisfiable core [2022-01-10 01:01:17,289 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:17,576 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-01-10 01:01:17,576 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:18,298 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 01:01:18,298 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2136599271] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:18,298 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:18,298 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 16] total 31 [2022-01-10 01:01:18,298 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1343384637] [2022-01-10 01:01:18,298 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:18,299 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2022-01-10 01:01:18,299 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:18,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2022-01-10 01:01:18,300 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=829, Unknown=0, NotChecked=0, Total=930 [2022-01-10 01:01:18,300 INFO L87 Difference]: Start difference. First operand 75 states and 96 transitions. Second operand has 31 states, 26 states have (on average 2.3846153846153846) internal successors, (62), 27 states have internal predecessors, (62), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (13), 7 states have call predecessors, (13), 12 states have call successors, (13) [2022-01-10 01:01:18,611 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:18,611 INFO L93 Difference]: Finished difference Result 84 states and 107 transitions. [2022-01-10 01:01:18,611 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-01-10 01:01:18,612 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 26 states have (on average 2.3846153846153846) internal successors, (62), 27 states have internal predecessors, (62), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (13), 7 states have call predecessors, (13), 12 states have call successors, (13) Word has length 43 [2022-01-10 01:01:18,612 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:18,612 INFO L225 Difference]: With dead ends: 84 [2022-01-10 01:01:18,613 INFO L226 Difference]: Without dead ends: 75 [2022-01-10 01:01:18,613 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 67 SyntacticMatches, 9 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 323 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=186, Invalid=1220, Unknown=0, NotChecked=0, Total=1406 [2022-01-10 01:01:18,614 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 30 mSDsluCounter, 251 mSDsCounter, 0 mSdLazyCounter, 350 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 274 SdHoareTripleChecker+Invalid, 356 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 350 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:18,614 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 274 Invalid, 356 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 350 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-01-10 01:01:18,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2022-01-10 01:01:18,618 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 70. [2022-01-10 01:01:18,618 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 48 states have (on average 1.125) internal successors, (54), 50 states have internal predecessors, (54), 10 states have call successors, (10), 4 states have call predecessors, (10), 11 states have return successors, (24), 15 states have call predecessors, (24), 10 states have call successors, (24) [2022-01-10 01:01:18,619 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 88 transitions. [2022-01-10 01:01:18,619 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 88 transitions. Word has length 43 [2022-01-10 01:01:18,619 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:18,619 INFO L470 AbstractCegarLoop]: Abstraction has 70 states and 88 transitions. [2022-01-10 01:01:18,619 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 26 states have (on average 2.3846153846153846) internal successors, (62), 27 states have internal predecessors, (62), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (13), 7 states have call predecessors, (13), 12 states have call successors, (13) [2022-01-10 01:01:18,619 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 88 transitions. [2022-01-10 01:01:18,620 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-01-10 01:01:18,620 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:18,620 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:18,643 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2022-01-10 01:01:18,835 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-01-10 01:01:18,836 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:18,836 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:18,836 INFO L85 PathProgramCache]: Analyzing trace with hash -1270773450, now seen corresponding path program 1 times [2022-01-10 01:01:18,836 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:18,836 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2116857108] [2022-01-10 01:01:18,836 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:18,837 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:18,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:18,859 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:18,862 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:18,880 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:18,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:18,923 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:18,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:18,956 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-01-10 01:01:18,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:18,988 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:18,990 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:19,008 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 6 proven. 8 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2022-01-10 01:01:19,009 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:19,009 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2116857108] [2022-01-10 01:01:19,009 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2116857108] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:19,009 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1634711350] [2022-01-10 01:01:19,009 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:19,009 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:19,009 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:19,010 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:19,039 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-01-10 01:01:19,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:19,077 INFO L263 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 27 conjunts are in the unsatisfiable core [2022-01-10 01:01:19,079 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:19,403 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 5 proven. 9 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2022-01-10 01:01:19,403 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:20,210 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 1 proven. 16 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-01-10 01:01:20,210 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1634711350] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:20,210 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:20,210 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15, 17] total 34 [2022-01-10 01:01:20,211 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1173492255] [2022-01-10 01:01:20,211 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:20,213 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2022-01-10 01:01:20,213 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:20,213 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2022-01-10 01:01:20,213 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=1008, Unknown=0, NotChecked=0, Total=1122 [2022-01-10 01:01:20,214 INFO L87 Difference]: Start difference. First operand 70 states and 88 transitions. Second operand has 34 states, 31 states have (on average 2.225806451612903) internal successors, (69), 27 states have internal predecessors, (69), 12 states have call successors, (12), 1 states have call predecessors, (12), 9 states have return successors, (13), 9 states have call predecessors, (13), 12 states have call successors, (13) [2022-01-10 01:01:20,688 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:20,688 INFO L93 Difference]: Finished difference Result 112 states and 148 transitions. [2022-01-10 01:01:20,688 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-01-10 01:01:20,688 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 31 states have (on average 2.225806451612903) internal successors, (69), 27 states have internal predecessors, (69), 12 states have call successors, (12), 1 states have call predecessors, (12), 9 states have return successors, (13), 9 states have call predecessors, (13), 12 states have call successors, (13) Word has length 44 [2022-01-10 01:01:20,688 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:20,691 INFO L225 Difference]: With dead ends: 112 [2022-01-10 01:01:20,691 INFO L226 Difference]: Without dead ends: 108 [2022-01-10 01:01:20,692 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 69 SyntacticMatches, 8 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 489 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=279, Invalid=1791, Unknown=0, NotChecked=0, Total=2070 [2022-01-10 01:01:20,693 INFO L933 BasicCegarLoop]: 28 mSDtfsCounter, 67 mSDsluCounter, 393 mSDsCounter, 0 mSdLazyCounter, 604 mSolverCounterSat, 59 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 76 SdHoareTripleChecker+Valid, 421 SdHoareTripleChecker+Invalid, 663 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 59 IncrementalHoareTripleChecker+Valid, 604 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:20,693 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [76 Valid, 421 Invalid, 663 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [59 Valid, 604 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-01-10 01:01:20,693 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2022-01-10 01:01:20,699 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 82. [2022-01-10 01:01:20,699 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 56 states have (on average 1.1071428571428572) internal successors, (62), 57 states have internal predecessors, (62), 11 states have call successors, (11), 4 states have call predecessors, (11), 14 states have return successors, (32), 20 states have call predecessors, (32), 11 states have call successors, (32) [2022-01-10 01:01:20,699 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 105 transitions. [2022-01-10 01:01:20,700 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 105 transitions. Word has length 44 [2022-01-10 01:01:20,700 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:20,700 INFO L470 AbstractCegarLoop]: Abstraction has 82 states and 105 transitions. [2022-01-10 01:01:20,700 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 31 states have (on average 2.225806451612903) internal successors, (69), 27 states have internal predecessors, (69), 12 states have call successors, (12), 1 states have call predecessors, (12), 9 states have return successors, (13), 9 states have call predecessors, (13), 12 states have call successors, (13) [2022-01-10 01:01:20,700 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 105 transitions. [2022-01-10 01:01:20,701 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-01-10 01:01:20,701 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:20,701 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:20,721 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-01-10 01:01:20,915 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-01-10 01:01:20,915 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:20,916 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:20,916 INFO L85 PathProgramCache]: Analyzing trace with hash 132450678, now seen corresponding path program 2 times [2022-01-10 01:01:20,916 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:20,916 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1107670542] [2022-01-10 01:01:20,916 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:20,916 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:20,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:20,937 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:20,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:20,959 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:20,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:20,973 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:20,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:20,994 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-01-10 01:01:20,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:21,019 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:21,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:21,034 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2022-01-10 01:01:21,034 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:21,035 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1107670542] [2022-01-10 01:01:21,035 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1107670542] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:21,035 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1274406002] [2022-01-10 01:01:21,035 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-01-10 01:01:21,035 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:21,035 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:21,036 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:21,044 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-01-10 01:01:21,109 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-01-10 01:01:21,109 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 01:01:21,110 INFO L263 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 25 conjunts are in the unsatisfiable core [2022-01-10 01:01:21,113 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:21,321 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2022-01-10 01:01:21,321 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:21,959 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-01-10 01:01:21,959 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1274406002] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:21,959 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:21,959 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 14] total 21 [2022-01-10 01:01:21,959 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1145757381] [2022-01-10 01:01:21,959 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:21,960 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-01-10 01:01:21,960 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:21,960 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-01-10 01:01:21,960 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=362, Unknown=0, NotChecked=0, Total=420 [2022-01-10 01:01:21,960 INFO L87 Difference]: Start difference. First operand 82 states and 105 transitions. Second operand has 21 states, 20 states have (on average 2.75) internal successors, (55), 18 states have internal predecessors, (55), 8 states have call successors, (11), 1 states have call predecessors, (11), 5 states have return successors, (11), 5 states have call predecessors, (11), 8 states have call successors, (11) [2022-01-10 01:01:22,178 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:22,179 INFO L93 Difference]: Finished difference Result 109 states and 142 transitions. [2022-01-10 01:01:22,179 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-01-10 01:01:22,179 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.75) internal successors, (55), 18 states have internal predecessors, (55), 8 states have call successors, (11), 1 states have call predecessors, (11), 5 states have return successors, (11), 5 states have call predecessors, (11), 8 states have call successors, (11) Word has length 44 [2022-01-10 01:01:22,179 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:22,180 INFO L225 Difference]: With dead ends: 109 [2022-01-10 01:01:22,180 INFO L226 Difference]: Without dead ends: 105 [2022-01-10 01:01:22,181 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 72 SyntacticMatches, 16 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=109, Invalid=593, Unknown=0, NotChecked=0, Total=702 [2022-01-10 01:01:22,182 INFO L933 BasicCegarLoop]: 25 mSDtfsCounter, 25 mSDsluCounter, 288 mSDsCounter, 0 mSdLazyCounter, 365 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 313 SdHoareTripleChecker+Invalid, 370 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 365 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:22,182 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 313 Invalid, 370 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 365 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-01-10 01:01:22,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states. [2022-01-10 01:01:22,197 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 89. [2022-01-10 01:01:22,198 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 61 states have (on average 1.098360655737705) internal successors, (67), 61 states have internal predecessors, (67), 11 states have call successors, (11), 4 states have call predecessors, (11), 16 states have return successors, (38), 23 states have call predecessors, (38), 11 states have call successors, (38) [2022-01-10 01:01:22,198 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 116 transitions. [2022-01-10 01:01:22,199 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 116 transitions. Word has length 44 [2022-01-10 01:01:22,199 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:22,199 INFO L470 AbstractCegarLoop]: Abstraction has 89 states and 116 transitions. [2022-01-10 01:01:22,199 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.75) internal successors, (55), 18 states have internal predecessors, (55), 8 states have call successors, (11), 1 states have call predecessors, (11), 5 states have return successors, (11), 5 states have call predecessors, (11), 8 states have call successors, (11) [2022-01-10 01:01:22,199 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 116 transitions. [2022-01-10 01:01:22,200 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2022-01-10 01:01:22,200 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:22,200 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:22,216 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-01-10 01:01:22,403 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-01-10 01:01:22,403 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:22,404 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:22,404 INFO L85 PathProgramCache]: Analyzing trace with hash 815065250, now seen corresponding path program 3 times [2022-01-10 01:01:22,404 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:22,404 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1401047846] [2022-01-10 01:01:22,404 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:22,404 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:22,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:22,427 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:22,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:22,451 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:22,454 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:22,468 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:22,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:22,512 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:22,514 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:22,529 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2022-01-10 01:01:22,531 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:22,557 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:22,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:22,581 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 13 proven. 12 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-01-10 01:01:22,582 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:22,582 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1401047846] [2022-01-10 01:01:22,582 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1401047846] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:22,582 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [646118587] [2022-01-10 01:01:22,582 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-01-10 01:01:22,582 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:22,582 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:22,583 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:22,614 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-01-10 01:01:22,667 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-01-10 01:01:22,667 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 01:01:22,668 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 32 conjunts are in the unsatisfiable core [2022-01-10 01:01:22,670 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:23,090 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 11 proven. 13 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-01-10 01:01:23,091 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:26,072 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 3 proven. 30 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2022-01-10 01:01:26,073 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [646118587] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:26,073 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:26,073 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16, 20] total 44 [2022-01-10 01:01:26,073 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2046253080] [2022-01-10 01:01:26,073 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:26,073 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 44 states [2022-01-10 01:01:26,073 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:26,074 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2022-01-10 01:01:26,074 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=142, Invalid=1750, Unknown=0, NotChecked=0, Total=1892 [2022-01-10 01:01:26,075 INFO L87 Difference]: Start difference. First operand 89 states and 116 transitions. Second operand has 44 states, 41 states have (on average 2.1707317073170733) internal successors, (89), 32 states have internal predecessors, (89), 16 states have call successors, (18), 1 states have call predecessors, (18), 12 states have return successors, (18), 14 states have call predecessors, (18), 16 states have call successors, (18) [2022-01-10 01:01:26,881 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:26,881 INFO L93 Difference]: Finished difference Result 148 states and 196 transitions. [2022-01-10 01:01:26,881 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-01-10 01:01:26,881 INFO L78 Accepts]: Start accepts. Automaton has has 44 states, 41 states have (on average 2.1707317073170733) internal successors, (89), 32 states have internal predecessors, (89), 16 states have call successors, (18), 1 states have call predecessors, (18), 12 states have return successors, (18), 14 states have call predecessors, (18), 16 states have call successors, (18) Word has length 52 [2022-01-10 01:01:26,883 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:26,885 INFO L225 Difference]: With dead ends: 148 [2022-01-10 01:01:26,886 INFO L226 Difference]: Without dead ends: 144 [2022-01-10 01:01:26,888 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 82 SyntacticMatches, 4 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 578 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=329, Invalid=2977, Unknown=0, NotChecked=0, Total=3306 [2022-01-10 01:01:26,889 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 63 mSDsluCounter, 430 mSDsCounter, 0 mSdLazyCounter, 722 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 453 SdHoareTripleChecker+Invalid, 769 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 722 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:26,889 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [79 Valid, 453 Invalid, 769 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 722 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-01-10 01:01:26,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2022-01-10 01:01:26,900 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 97. [2022-01-10 01:01:26,901 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 67 states have (on average 1.0895522388059702) internal successors, (73), 65 states have internal predecessors, (73), 11 states have call successors, (11), 4 states have call predecessors, (11), 18 states have return successors, (44), 27 states have call predecessors, (44), 11 states have call successors, (44) [2022-01-10 01:01:26,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 128 transitions. [2022-01-10 01:01:26,902 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 128 transitions. Word has length 52 [2022-01-10 01:01:26,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:26,902 INFO L470 AbstractCegarLoop]: Abstraction has 97 states and 128 transitions. [2022-01-10 01:01:26,902 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 44 states, 41 states have (on average 2.1707317073170733) internal successors, (89), 32 states have internal predecessors, (89), 16 states have call successors, (18), 1 states have call predecessors, (18), 12 states have return successors, (18), 14 states have call predecessors, (18), 16 states have call successors, (18) [2022-01-10 01:01:26,902 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 128 transitions. [2022-01-10 01:01:26,903 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2022-01-10 01:01:26,903 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:26,903 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:26,923 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-01-10 01:01:27,111 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-01-10 01:01:27,111 INFO L402 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:27,112 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:27,112 INFO L85 PathProgramCache]: Analyzing trace with hash 850048834, now seen corresponding path program 4 times [2022-01-10 01:01:27,112 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:27,112 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [983758476] [2022-01-10 01:01:27,112 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:27,112 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:27,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:27,151 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:27,154 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:27,174 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:27,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:27,191 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:27,193 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:27,245 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:27,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:27,281 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2022-01-10 01:01:27,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:27,317 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:27,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:27,340 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 12 proven. 13 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-01-10 01:01:27,340 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:27,340 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [983758476] [2022-01-10 01:01:27,340 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [983758476] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:27,340 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [32763728] [2022-01-10 01:01:27,340 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-01-10 01:01:27,341 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:27,341 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:27,342 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:27,342 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-01-10 01:01:27,428 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-01-10 01:01:27,428 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 01:01:27,429 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 31 conjunts are in the unsatisfiable core [2022-01-10 01:01:27,431 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:27,808 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 11 proven. 14 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-01-10 01:01:27,808 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:28,860 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 5 proven. 28 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2022-01-10 01:01:28,860 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [32763728] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:28,860 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:28,860 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 16, 20] total 37 [2022-01-10 01:01:28,860 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2070755378] [2022-01-10 01:01:28,860 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:28,861 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2022-01-10 01:01:28,861 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:28,861 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2022-01-10 01:01:28,862 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=129, Invalid=1203, Unknown=0, NotChecked=0, Total=1332 [2022-01-10 01:01:28,862 INFO L87 Difference]: Start difference. First operand 97 states and 128 transitions. Second operand has 37 states, 34 states have (on average 2.264705882352941) internal successors, (77), 28 states have internal predecessors, (77), 13 states have call successors, (15), 1 states have call predecessors, (15), 9 states have return successors, (16), 11 states have call predecessors, (16), 13 states have call successors, (16) [2022-01-10 01:01:29,406 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:29,406 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2022-01-10 01:01:29,406 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2022-01-10 01:01:29,407 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 34 states have (on average 2.264705882352941) internal successors, (77), 28 states have internal predecessors, (77), 13 states have call successors, (15), 1 states have call predecessors, (15), 9 states have return successors, (16), 11 states have call predecessors, (16), 13 states have call successors, (16) Word has length 52 [2022-01-10 01:01:29,407 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:29,407 INFO L225 Difference]: With dead ends: 135 [2022-01-10 01:01:29,408 INFO L226 Difference]: Without dead ends: 131 [2022-01-10 01:01:29,408 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 85 SyntacticMatches, 9 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 627 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=345, Invalid=2205, Unknown=0, NotChecked=0, Total=2550 [2022-01-10 01:01:29,409 INFO L933 BasicCegarLoop]: 24 mSDtfsCounter, 43 mSDsluCounter, 311 mSDsCounter, 0 mSdLazyCounter, 622 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 335 SdHoareTripleChecker+Invalid, 658 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 622 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:29,409 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [50 Valid, 335 Invalid, 658 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 622 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-01-10 01:01:29,409 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2022-01-10 01:01:29,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 70. [2022-01-10 01:01:29,420 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 48 states have (on average 1.125) internal successors, (54), 50 states have internal predecessors, (54), 10 states have call successors, (10), 4 states have call predecessors, (10), 11 states have return successors, (22), 15 states have call predecessors, (22), 10 states have call successors, (22) [2022-01-10 01:01:29,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 86 transitions. [2022-01-10 01:01:29,421 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 86 transitions. Word has length 52 [2022-01-10 01:01:29,421 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:29,421 INFO L470 AbstractCegarLoop]: Abstraction has 70 states and 86 transitions. [2022-01-10 01:01:29,421 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 34 states have (on average 2.264705882352941) internal successors, (77), 28 states have internal predecessors, (77), 13 states have call successors, (15), 1 states have call predecessors, (15), 9 states have return successors, (16), 11 states have call predecessors, (16), 13 states have call successors, (16) [2022-01-10 01:01:29,421 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 86 transitions. [2022-01-10 01:01:29,422 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-01-10 01:01:29,422 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:29,422 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:29,444 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-01-10 01:01:29,639 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:29,639 INFO L402 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:29,640 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:29,640 INFO L85 PathProgramCache]: Analyzing trace with hash -2103225754, now seen corresponding path program 5 times [2022-01-10 01:01:29,640 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:29,640 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1751067707] [2022-01-10 01:01:29,640 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:29,640 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:29,647 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:29,667 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:29,670 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:29,688 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:29,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:29,721 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:29,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:29,741 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-01-10 01:01:29,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:29,768 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:29,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:29,785 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:29,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:29,825 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 5 proven. 13 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-01-10 01:01:29,825 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:29,825 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1751067707] [2022-01-10 01:01:29,825 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1751067707] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:29,825 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [410771378] [2022-01-10 01:01:29,825 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-01-10 01:01:29,826 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:29,826 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:29,827 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:29,856 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-01-10 01:01:29,935 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2022-01-10 01:01:29,935 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 01:01:29,936 INFO L263 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 31 conjunts are in the unsatisfiable core [2022-01-10 01:01:29,938 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:30,180 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 5 proven. 13 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-01-10 01:01:30,180 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:31,001 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-01-10 01:01:31,001 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [410771378] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:31,001 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:31,001 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 18] total 27 [2022-01-10 01:01:31,001 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1377442098] [2022-01-10 01:01:31,001 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:31,002 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2022-01-10 01:01:31,002 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:31,002 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2022-01-10 01:01:31,002 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=625, Unknown=0, NotChecked=0, Total=702 [2022-01-10 01:01:31,002 INFO L87 Difference]: Start difference. First operand 70 states and 86 transitions. Second operand has 27 states, 26 states have (on average 2.6153846153846154) internal successors, (68), 23 states have internal predecessors, (68), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (14), 7 states have call predecessors, (14), 12 states have call successors, (14) [2022-01-10 01:01:31,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:31,308 INFO L93 Difference]: Finished difference Result 97 states and 121 transitions. [2022-01-10 01:01:31,308 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-01-10 01:01:31,309 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 26 states have (on average 2.6153846153846154) internal successors, (68), 23 states have internal predecessors, (68), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (14), 7 states have call predecessors, (14), 12 states have call successors, (14) Word has length 51 [2022-01-10 01:01:31,309 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:31,309 INFO L225 Difference]: With dead ends: 97 [2022-01-10 01:01:31,310 INFO L226 Difference]: Without dead ends: 93 [2022-01-10 01:01:31,310 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 83 SyntacticMatches, 16 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 209 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=154, Invalid=1036, Unknown=0, NotChecked=0, Total=1190 [2022-01-10 01:01:31,311 INFO L933 BasicCegarLoop]: 30 mSDtfsCounter, 46 mSDsluCounter, 366 mSDsCounter, 0 mSdLazyCounter, 468 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 396 SdHoareTripleChecker+Invalid, 481 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 468 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:31,311 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [54 Valid, 396 Invalid, 481 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 468 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-01-10 01:01:31,311 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-01-10 01:01:31,315 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 73. [2022-01-10 01:01:31,316 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 50 states have (on average 1.12) internal successors, (56), 52 states have internal predecessors, (56), 10 states have call successors, (10), 4 states have call predecessors, (10), 12 states have return successors, (24), 16 states have call predecessors, (24), 10 states have call successors, (24) [2022-01-10 01:01:31,316 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 90 transitions. [2022-01-10 01:01:31,316 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 90 transitions. Word has length 51 [2022-01-10 01:01:31,316 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:31,316 INFO L470 AbstractCegarLoop]: Abstraction has 73 states and 90 transitions. [2022-01-10 01:01:31,317 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 26 states have (on average 2.6153846153846154) internal successors, (68), 23 states have internal predecessors, (68), 12 states have call successors, (12), 1 states have call predecessors, (12), 8 states have return successors, (14), 7 states have call predecessors, (14), 12 states have call successors, (14) [2022-01-10 01:01:31,317 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 90 transitions. [2022-01-10 01:01:31,317 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-01-10 01:01:31,317 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:31,317 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:31,345 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-01-10 01:01:31,534 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable19 [2022-01-10 01:01:31,535 INFO L402 AbstractCegarLoop]: === Iteration 21 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:31,535 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:31,535 INFO L85 PathProgramCache]: Analyzing trace with hash -262469082, now seen corresponding path program 6 times [2022-01-10 01:01:31,535 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:31,535 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [288628291] [2022-01-10 01:01:31,535 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:31,535 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:31,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:31,567 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:31,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:31,598 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:31,607 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:31,628 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:31,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:31,663 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-01-10 01:01:31,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:31,704 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:31,706 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:31,744 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:31,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:31,771 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 5 proven. 15 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2022-01-10 01:01:31,772 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:31,772 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [288628291] [2022-01-10 01:01:31,772 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [288628291] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:31,772 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1173762794] [2022-01-10 01:01:31,772 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-01-10 01:01:31,772 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:31,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:31,773 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:31,775 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-01-10 01:01:31,879 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2022-01-10 01:01:31,879 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 01:01:31,880 INFO L263 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 30 conjunts are in the unsatisfiable core [2022-01-10 01:01:31,883 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:32,295 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 5 proven. 15 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2022-01-10 01:01:32,295 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:33,081 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2022-01-10 01:01:33,081 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1173762794] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:33,081 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:33,081 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16, 17] total 33 [2022-01-10 01:01:33,081 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1062980282] [2022-01-10 01:01:33,081 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:33,081 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2022-01-10 01:01:33,081 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:33,082 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2022-01-10 01:01:33,082 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=950, Unknown=0, NotChecked=0, Total=1056 [2022-01-10 01:01:33,082 INFO L87 Difference]: Start difference. First operand 73 states and 90 transitions. Second operand has 33 states, 28 states have (on average 2.392857142857143) internal successors, (67), 27 states have internal predecessors, (67), 12 states have call successors, (15), 1 states have call predecessors, (15), 8 states have return successors, (16), 9 states have call predecessors, (16), 12 states have call successors, (16) [2022-01-10 01:01:33,451 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:33,451 INFO L93 Difference]: Finished difference Result 91 states and 115 transitions. [2022-01-10 01:01:33,451 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-01-10 01:01:33,451 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 28 states have (on average 2.392857142857143) internal successors, (67), 27 states have internal predecessors, (67), 12 states have call successors, (15), 1 states have call predecessors, (15), 8 states have return successors, (16), 9 states have call predecessors, (16), 12 states have call successors, (16) Word has length 51 [2022-01-10 01:01:33,451 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:33,452 INFO L225 Difference]: With dead ends: 91 [2022-01-10 01:01:33,452 INFO L226 Difference]: Without dead ends: 82 [2022-01-10 01:01:33,453 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 82 SyntacticMatches, 12 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 402 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=201, Invalid=1439, Unknown=0, NotChecked=0, Total=1640 [2022-01-10 01:01:33,453 INFO L933 BasicCegarLoop]: 24 mSDtfsCounter, 20 mSDsluCounter, 298 mSDsCounter, 0 mSdLazyCounter, 425 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 322 SdHoareTripleChecker+Invalid, 429 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 425 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:33,453 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 322 Invalid, 429 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 425 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-01-10 01:01:33,454 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2022-01-10 01:01:33,457 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 74. [2022-01-10 01:01:33,458 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 51 states have (on average 1.1176470588235294) internal successors, (57), 52 states have internal predecessors, (57), 10 states have call successors, (10), 4 states have call predecessors, (10), 12 states have return successors, (24), 17 states have call predecessors, (24), 10 states have call successors, (24) [2022-01-10 01:01:33,458 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 91 transitions. [2022-01-10 01:01:33,458 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 91 transitions. Word has length 51 [2022-01-10 01:01:33,458 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:33,459 INFO L470 AbstractCegarLoop]: Abstraction has 74 states and 91 transitions. [2022-01-10 01:01:33,459 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 28 states have (on average 2.392857142857143) internal successors, (67), 27 states have internal predecessors, (67), 12 states have call successors, (15), 1 states have call predecessors, (15), 8 states have return successors, (16), 9 states have call predecessors, (16), 12 states have call successors, (16) [2022-01-10 01:01:33,459 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 91 transitions. [2022-01-10 01:01:33,459 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-01-10 01:01:33,459 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:33,460 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:33,487 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-01-10 01:01:33,675 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:33,675 INFO L402 AbstractCegarLoop]: === Iteration 22 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:33,676 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:33,676 INFO L85 PathProgramCache]: Analyzing trace with hash 334535194, now seen corresponding path program 4 times [2022-01-10 01:01:33,676 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:33,676 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1823222665] [2022-01-10 01:01:33,676 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:33,676 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:33,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:33,699 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:33,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:33,721 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:33,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:33,751 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:33,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:33,794 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:33,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:33,813 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2022-01-10 01:01:33,815 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:33,845 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:33,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:33,870 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:33,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:33,894 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 15 proven. 21 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-01-10 01:01:33,894 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:33,894 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1823222665] [2022-01-10 01:01:33,894 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1823222665] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:33,894 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [739005650] [2022-01-10 01:01:33,894 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-01-10 01:01:33,894 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:33,894 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:33,895 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:33,897 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-01-10 01:01:34,011 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-01-10 01:01:34,011 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 01:01:34,012 INFO L263 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 38 conjunts are in the unsatisfiable core [2022-01-10 01:01:34,014 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:34,522 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 10 proven. 22 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-01-10 01:01:34,522 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:35,876 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [739005650] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:35,877 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-10 01:01:35,877 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 31 [2022-01-10 01:01:35,877 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1005569063] [2022-01-10 01:01:35,877 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:35,877 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2022-01-10 01:01:35,877 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:35,877 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2022-01-10 01:01:35,878 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=1440, Unknown=0, NotChecked=0, Total=1560 [2022-01-10 01:01:35,878 INFO L87 Difference]: Start difference. First operand 74 states and 91 transitions. Second operand has 31 states, 28 states have (on average 2.107142857142857) internal successors, (59), 23 states have internal predecessors, (59), 11 states have call successors, (11), 1 states have call predecessors, (11), 11 states have return successors, (14), 11 states have call predecessors, (14), 11 states have call successors, (14) [2022-01-10 01:01:36,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:36,453 INFO L93 Difference]: Finished difference Result 106 states and 134 transitions. [2022-01-10 01:01:36,455 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-01-10 01:01:36,455 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 28 states have (on average 2.107142857142857) internal successors, (59), 23 states have internal predecessors, (59), 11 states have call successors, (11), 1 states have call predecessors, (11), 11 states have return successors, (14), 11 states have call predecessors, (14), 11 states have call successors, (14) Word has length 59 [2022-01-10 01:01:36,455 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:36,456 INFO L225 Difference]: With dead ends: 106 [2022-01-10 01:01:36,456 INFO L226 Difference]: Without dead ends: 102 [2022-01-10 01:01:36,457 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 72 SyntacticMatches, 6 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 367 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=239, Invalid=2211, Unknown=0, NotChecked=0, Total=2450 [2022-01-10 01:01:36,457 INFO L933 BasicCegarLoop]: 29 mSDtfsCounter, 40 mSDsluCounter, 490 mSDsCounter, 0 mSdLazyCounter, 700 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 519 SdHoareTripleChecker+Invalid, 718 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 700 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:36,457 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [54 Valid, 519 Invalid, 718 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 700 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-01-10 01:01:36,458 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2022-01-10 01:01:36,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 76. [2022-01-10 01:01:36,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 52 states have (on average 1.1153846153846154) internal successors, (58), 54 states have internal predecessors, (58), 10 states have call successors, (10), 4 states have call predecessors, (10), 13 states have return successors, (27), 17 states have call predecessors, (27), 10 states have call successors, (27) [2022-01-10 01:01:36,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 95 transitions. [2022-01-10 01:01:36,463 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 95 transitions. Word has length 59 [2022-01-10 01:01:36,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:36,463 INFO L470 AbstractCegarLoop]: Abstraction has 76 states and 95 transitions. [2022-01-10 01:01:36,463 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 28 states have (on average 2.107142857142857) internal successors, (59), 23 states have internal predecessors, (59), 11 states have call successors, (11), 1 states have call predecessors, (11), 11 states have return successors, (14), 11 states have call predecessors, (14), 11 states have call successors, (14) [2022-01-10 01:01:36,463 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 95 transitions. [2022-01-10 01:01:36,464 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-01-10 01:01:36,464 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:36,464 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:36,483 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2022-01-10 01:01:36,675 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:36,676 INFO L402 AbstractCegarLoop]: === Iteration 23 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:36,676 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:36,676 INFO L85 PathProgramCache]: Analyzing trace with hash 1972765050, now seen corresponding path program 7 times [2022-01-10 01:01:36,676 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:36,676 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1986965921] [2022-01-10 01:01:36,676 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:36,676 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:36,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:36,699 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:36,702 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:36,722 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:36,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:36,737 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:36,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:36,767 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:36,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:36,783 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2022-01-10 01:01:36,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:36,822 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:36,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:36,844 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:36,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:36,866 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 11 proven. 18 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2022-01-10 01:01:36,866 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:36,866 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1986965921] [2022-01-10 01:01:36,866 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1986965921] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:36,866 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1118722640] [2022-01-10 01:01:36,866 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-01-10 01:01:36,866 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:36,867 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:36,872 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:36,873 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-01-10 01:01:36,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:36,984 INFO L263 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 35 conjunts are in the unsatisfiable core [2022-01-10 01:01:36,985 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:37,255 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 11 proven. 18 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2022-01-10 01:01:37,255 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:38,469 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 0 proven. 38 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-01-10 01:01:38,469 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1118722640] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-10 01:01:38,469 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-01-10 01:01:38,469 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16, 19] total 28 [2022-01-10 01:01:38,469 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2009893101] [2022-01-10 01:01:38,469 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-01-10 01:01:38,469 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2022-01-10 01:01:38,470 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-10 01:01:38,470 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2022-01-10 01:01:38,470 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=677, Unknown=0, NotChecked=0, Total=756 [2022-01-10 01:01:38,470 INFO L87 Difference]: Start difference. First operand 76 states and 95 transitions. Second operand has 28 states, 27 states have (on average 2.6666666666666665) internal successors, (72), 23 states have internal predecessors, (72), 12 states have call successors, (15), 1 states have call predecessors, (15), 8 states have return successors, (17), 8 states have call predecessors, (17), 12 states have call successors, (17) [2022-01-10 01:01:38,835 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-10 01:01:38,835 INFO L93 Difference]: Finished difference Result 109 states and 138 transitions. [2022-01-10 01:01:38,835 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-01-10 01:01:38,836 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 27 states have (on average 2.6666666666666665) internal successors, (72), 23 states have internal predecessors, (72), 12 states have call successors, (15), 1 states have call predecessors, (15), 8 states have return successors, (17), 8 states have call predecessors, (17), 12 states have call successors, (17) Word has length 59 [2022-01-10 01:01:38,836 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-10 01:01:38,837 INFO L225 Difference]: With dead ends: 109 [2022-01-10 01:01:38,837 INFO L226 Difference]: Without dead ends: 105 [2022-01-10 01:01:38,837 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 97 SyntacticMatches, 21 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 241 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=166, Invalid=1166, Unknown=0, NotChecked=0, Total=1332 [2022-01-10 01:01:38,838 INFO L933 BasicCegarLoop]: 27 mSDtfsCounter, 67 mSDsluCounter, 387 mSDsCounter, 0 mSdLazyCounter, 526 mSolverCounterSat, 56 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 414 SdHoareTripleChecker+Invalid, 582 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 56 IncrementalHoareTripleChecker+Valid, 526 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-01-10 01:01:38,838 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [79 Valid, 414 Invalid, 582 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [56 Valid, 526 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-01-10 01:01:38,838 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states. [2022-01-10 01:01:38,843 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 84. [2022-01-10 01:01:38,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 58 states have (on average 1.103448275862069) internal successors, (64), 58 states have internal predecessors, (64), 10 states have call successors, (10), 4 states have call predecessors, (10), 15 states have return successors, (33), 21 states have call predecessors, (33), 10 states have call successors, (33) [2022-01-10 01:01:38,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 107 transitions. [2022-01-10 01:01:38,844 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 107 transitions. Word has length 59 [2022-01-10 01:01:38,844 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-10 01:01:38,844 INFO L470 AbstractCegarLoop]: Abstraction has 84 states and 107 transitions. [2022-01-10 01:01:38,844 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 27 states have (on average 2.6666666666666665) internal successors, (72), 23 states have internal predecessors, (72), 12 states have call successors, (15), 1 states have call predecessors, (15), 8 states have return successors, (17), 8 states have call predecessors, (17), 12 states have call successors, (17) [2022-01-10 01:01:38,845 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 107 transitions. [2022-01-10 01:01:38,845 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-01-10 01:01:38,845 INFO L506 BasicCegarLoop]: Found error trace [2022-01-10 01:01:38,845 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-10 01:01:38,863 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2022-01-10 01:01:39,051 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable22 [2022-01-10 01:01:39,052 INFO L402 AbstractCegarLoop]: === Iteration 24 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [gcdErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-10 01:01:39,052 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-10 01:01:39,052 INFO L85 PathProgramCache]: Analyzing trace with hash -1626138758, now seen corresponding path program 8 times [2022-01-10 01:01:39,052 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-10 01:01:39,052 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1394728096] [2022-01-10 01:01:39,052 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-10 01:01:39,052 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-10 01:01:39,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:39,077 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-10 01:01:39,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:39,100 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:39,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:39,150 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:39,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:39,225 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-01-10 01:01:39,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:39,245 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2022-01-10 01:01:39,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:39,280 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:39,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:39,304 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-01-10 01:01:39,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-10 01:01:39,326 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 8 proven. 26 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-01-10 01:01:39,327 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-10 01:01:39,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1394728096] [2022-01-10 01:01:39,327 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1394728096] provided 0 perfect and 1 imperfect interpolant sequences [2022-01-10 01:01:39,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [893852953] [2022-01-10 01:01:39,327 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-01-10 01:01:39,327 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-10 01:01:39,327 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-10 01:01:39,328 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-10 01:01:39,350 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-01-10 01:01:39,465 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-01-10 01:01:39,466 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-01-10 01:01:39,466 INFO L263 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 37 conjunts are in the unsatisfiable core [2022-01-10 01:01:39,467 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-10 01:01:40,024 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 10 proven. 24 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-01-10 01:01:40,024 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-10 01:01:52,681 WARN L838 $PredicateComparison]: unable to prove that (forall ((|aux_div_aux_div_v_gcd_#in~y2_BEFORE_CALL_19_77_121| Int)) (or (and (<= 0 (+ 2 |aux_div_aux_div_v_gcd_#in~y2_BEFORE_CALL_19_77_121| (div (+ (* (- 1) (div (+ 6 |c_gcd_#in~y2|) (- 2))) (* (- 1) |c_gcd_#res|) (- 3)) 2))) (forall ((|aux_div_v_gcd_#t~ret4_AFTER_RETURN_18_307| Int)) (or (and (forall ((|aux_div_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_83| Int) (|aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_83| Int)) (or (<= (+ (* |aux_div_v_gcd_#t~ret4_AFTER_RETURN_18_307| 2) 2 |c_gcd_#res| |aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_83|) (+ (* 2 |aux_div_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_83|) |c_gcd_#in~y2|)) (>= |aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_83| 2) (<= (div (+ 6 |c_gcd_#in~y2|) (- 2)) (+ (div (+ (* |aux_div_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_83| (- 4)) (* 2 |aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_83|) (* (- 2) |c_gcd_#in~y2|) (- 8)) 4) 1 (* 2 |aux_div_aux_div_v_gcd_#in~y2_BEFORE_CALL_19_77_121|))) (> 0 |aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_83|) (<= (+ 2 |aux_div_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_83|) 0))) (forall ((|aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80| Int) (|aux_div_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80| Int) (aux_div_aux_div_aux_mod_v_gcd_~y2_BEFORE_CALL_36_52_89_139 Int)) (let ((.cse1 (div (+ 2 (* 2 |aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80|) (* |aux_div_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80| 4)) (- 4))) (.cse3 (* 2 aux_div_aux_div_aux_mod_v_gcd_~y2_BEFORE_CALL_36_52_89_139)) (.cse2 (* 2 |aux_div_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80|)) (.cse0 (div (+ 6 |c_gcd_#in~y2|) (- 2))) (.cse4 (div (+ (* (- 2) |aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80|) (* |aux_div_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80| (- 4)) (- 8)) 4)) (.cse5 (* 2 |aux_div_aux_div_v_gcd_#in~y2_BEFORE_CALL_19_77_121|))) (or (< (+ 2 aux_div_aux_div_aux_mod_v_gcd_~y2_BEFORE_CALL_36_52_89_139) 0) (> 0 |aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80|) (<= (+ .cse0 .cse1 .cse2 |aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80|) (+ .cse3 .cse4)) (<= (+ .cse1 3 .cse2 |aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80| .cse5) .cse3) (>= |aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80| 2) (<= (+ .cse3 1) (+ |aux_div_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80| .cse5)) (<= (+ (* |aux_div_v_gcd_#t~ret4_AFTER_RETURN_18_307| 2) 2 |c_gcd_#res|) (+ .cse2 |aux_mod_aux_div_aux_mod_v_gcd_#in~y2_BEFORE_CALL_19_77_220_80|)) (<= .cse0 (+ .cse4 1 .cse5)))))) (<= 0 (+ 3 (* |aux_div_v_gcd_#t~ret4_AFTER_RETURN_18_307| 3)))))) (< (+ 2 |aux_div_aux_div_v_gcd_#in~y2_BEFORE_CALL_19_77_121|) 0))) is different from false