./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c3fed411 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash f4db5fb03820aea666082345ea177387bf1c218ce33dad19402cb646ed5abf58 --- Real Ultimate output --- This is Ultimate 0.2.2-tmp.no-commuhash-c3fed41 [2021-12-16 03:21:49,958 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-16 03:21:49,982 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-16 03:21:50,000 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-16 03:21:50,000 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-16 03:21:50,001 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-16 03:21:50,002 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-16 03:21:50,003 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-16 03:21:50,004 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-16 03:21:50,005 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-16 03:21:50,006 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-16 03:21:50,006 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-16 03:21:50,007 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-16 03:21:50,007 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-16 03:21:50,008 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-16 03:21:50,009 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-16 03:21:50,010 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-16 03:21:50,010 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-16 03:21:50,012 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-16 03:21:50,013 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-16 03:21:50,014 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-16 03:21:50,015 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-16 03:21:50,015 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-16 03:21:50,016 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-16 03:21:50,018 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-16 03:21:50,018 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-16 03:21:50,018 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-16 03:21:50,019 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-16 03:21:50,019 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-16 03:21:50,020 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-16 03:21:50,020 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-16 03:21:50,020 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-16 03:21:50,021 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-16 03:21:50,021 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-16 03:21:50,022 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-16 03:21:50,022 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-16 03:21:50,023 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-16 03:21:50,024 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-16 03:21:50,024 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-16 03:21:50,024 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-16 03:21:50,026 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-16 03:21:50,026 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2021-12-16 03:21:50,045 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-16 03:21:50,045 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-16 03:21:50,046 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-16 03:21:50,046 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-16 03:21:50,047 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-16 03:21:50,047 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-16 03:21:50,047 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-16 03:21:50,047 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-16 03:21:50,048 INFO L138 SettingsManager]: * Use SBE=true [2021-12-16 03:21:50,048 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-16 03:21:50,048 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-16 03:21:50,048 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-16 03:21:50,049 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-12-16 03:21:50,049 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-16 03:21:50,049 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-12-16 03:21:50,049 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-16 03:21:50,049 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-16 03:21:50,049 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-12-16 03:21:50,050 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-16 03:21:50,050 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-16 03:21:50,050 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-16 03:21:50,050 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-16 03:21:50,050 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-16 03:21:50,050 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-16 03:21:50,050 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-12-16 03:21:50,050 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-16 03:21:50,051 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-16 03:21:50,052 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-12-16 03:21:50,052 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2021-12-16 03:21:50,052 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-12-16 03:21:50,052 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-16 03:21:50,052 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.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> f4db5fb03820aea666082345ea177387bf1c218ce33dad19402cb646ed5abf58 [2021-12-16 03:21:50,253 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-16 03:21:50,271 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-16 03:21:50,273 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-16 03:21:50,274 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-16 03:21:50,287 INFO L275 PluginConnector]: CDTParser initialized [2021-12-16 03:21:50,288 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i [2021-12-16 03:21:50,346 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/34e75046f/3ca04f59097946e2baef161fbe199c70/FLAGf51dafc74 [2021-12-16 03:21:50,918 INFO L306 CDTParser]: Found 1 translation units. [2021-12-16 03:21:50,919 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i [2021-12-16 03:21:50,951 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/34e75046f/3ca04f59097946e2baef161fbe199c70/FLAGf51dafc74 [2021-12-16 03:21:51,362 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/34e75046f/3ca04f59097946e2baef161fbe199c70 [2021-12-16 03:21:51,363 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-16 03:21:51,364 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-16 03:21:51,366 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-16 03:21:51,366 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-16 03:21:51,368 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-16 03:21:51,368 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.12 03:21:51" (1/1) ... [2021-12-16 03:21:51,369 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3956bd5a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:51, skipping insertion in model container [2021-12-16 03:21:51,369 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.12 03:21:51" (1/1) ... [2021-12-16 03:21:51,374 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-16 03:21:51,451 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-16 03:21:51,729 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i[4505,4518] [2021-12-16 03:21:51,738 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i[4565,4578] [2021-12-16 03:21:52,251 WARN L610 FunctionHandler]: implicit declaration of function __builtin_va_copy [2021-12-16 03:21:52,312 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,321 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,322 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,322 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,323 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,330 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,331 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,333 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,333 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,577 WARN L610 FunctionHandler]: implicit declaration of function __atomic_load_n [2021-12-16 03:21:52,578 WARN L610 FunctionHandler]: implicit declaration of function __atomic_store_n [2021-12-16 03:21:52,579 WARN L610 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2021-12-16 03:21:52,588 WARN L610 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2021-12-16 03:21:52,590 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2021-12-16 03:21:52,592 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2021-12-16 03:21:52,594 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2021-12-16 03:21:52,596 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2021-12-16 03:21:52,597 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2021-12-16 03:21:52,597 WARN L610 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2021-12-16 03:21:52,725 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,725 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,765 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-16 03:21:52,807 INFO L203 MainTranslator]: Completed pre-run [2021-12-16 03:21:52,830 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i[4505,4518] [2021-12-16 03:21:52,830 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_priority_queue_init_dynamic_harness-1.i[4565,4578] [2021-12-16 03:21:52,873 WARN L610 FunctionHandler]: implicit declaration of function __builtin_va_copy [2021-12-16 03:21:52,881 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,881 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,882 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,882 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,882 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,886 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,886 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,887 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,887 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,920 WARN L610 FunctionHandler]: implicit declaration of function __atomic_load_n [2021-12-16 03:21:52,921 WARN L610 FunctionHandler]: implicit declaration of function __atomic_store_n [2021-12-16 03:21:52,921 WARN L610 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2021-12-16 03:21:52,922 WARN L610 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2021-12-16 03:21:52,923 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2021-12-16 03:21:52,923 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2021-12-16 03:21:52,923 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2021-12-16 03:21:52,924 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2021-12-16 03:21:52,924 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2021-12-16 03:21:52,924 WARN L610 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2021-12-16 03:21:52,964 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:52,965 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-16 03:21:53,008 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-16 03:21:53,146 INFO L208 MainTranslator]: Completed translation [2021-12-16 03:21:53,147 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53 WrapperNode [2021-12-16 03:21:53,147 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-16 03:21:53,148 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-16 03:21:53,148 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-16 03:21:53,148 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-16 03:21:53,152 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53" (1/1) ... [2021-12-16 03:21:53,212 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53" (1/1) ... [2021-12-16 03:21:53,270 INFO L137 Inliner]: procedures = 689, calls = 1517, calls flagged for inlining = 52, calls inlined = 9, statements flattened = 742 [2021-12-16 03:21:53,271 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-16 03:21:53,272 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-16 03:21:53,272 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-16 03:21:53,272 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-16 03:21:53,278 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53" (1/1) ... [2021-12-16 03:21:53,278 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53" (1/1) ... [2021-12-16 03:21:53,283 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53" (1/1) ... [2021-12-16 03:21:53,283 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53" (1/1) ... [2021-12-16 03:21:53,309 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53" (1/1) ... [2021-12-16 03:21:53,342 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53" (1/1) ... [2021-12-16 03:21:53,348 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53" (1/1) ... [2021-12-16 03:21:53,381 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-16 03:21:53,382 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-16 03:21:53,382 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-16 03:21:53,382 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-16 03:21:53,383 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53" (1/1) ... [2021-12-16 03:21:53,403 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-16 03:21:53,413 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:21:53,443 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) [2021-12-16 03:21:53,468 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 [2021-12-16 03:21:53,498 INFO L130 BoogieDeclarations]: Found specification of procedure aws_is_mem_zeroed [2021-12-16 03:21:53,499 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_is_mem_zeroed [2021-12-16 03:21:53,499 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-12-16 03:21:53,499 INFO L130 BoogieDeclarations]: Found specification of procedure aws_array_list_is_valid [2021-12-16 03:21:53,499 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_array_list_is_valid [2021-12-16 03:21:53,500 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_bool [2021-12-16 03:21:53,500 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_bool [2021-12-16 03:21:53,500 INFO L130 BoogieDeclarations]: Found specification of procedure aws_allocator_is_valid [2021-12-16 03:21:53,501 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_allocator_is_valid [2021-12-16 03:21:53,504 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2021-12-16 03:21:53,505 INFO L130 BoogieDeclarations]: Found specification of procedure aws_raise_error [2021-12-16 03:21:53,505 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_raise_error [2021-12-16 03:21:53,505 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-12-16 03:21:53,506 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-12-16 03:21:53,507 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-12-16 03:21:53,507 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-16 03:21:53,507 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-12-16 03:21:53,507 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-16 03:21:53,508 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-16 03:21:53,508 INFO L130 BoogieDeclarations]: Found specification of procedure bounded_malloc [2021-12-16 03:21:53,508 INFO L138 BoogieDeclarations]: Found implementation of procedure bounded_malloc [2021-12-16 03:21:53,508 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_size_t [2021-12-16 03:21:53,508 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_size_t [2021-12-16 03:21:53,508 INFO L130 BoogieDeclarations]: Found specification of procedure aws_mul_size_checked [2021-12-16 03:21:53,509 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_mul_size_checked [2021-12-16 03:21:53,509 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_malloc [2021-12-16 03:21:53,510 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_malloc [2021-12-16 03:21:53,510 INFO L130 BoogieDeclarations]: Found specification of procedure aws_priority_queue_is_valid [2021-12-16 03:21:53,510 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_priority_queue_is_valid [2021-12-16 03:21:53,510 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-12-16 03:21:53,511 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-12-16 03:21:53,511 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-12-16 03:21:53,511 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-12-16 03:21:53,511 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2021-12-16 03:21:53,511 INFO L130 BoogieDeclarations]: Found specification of procedure can_fail_allocator [2021-12-16 03:21:53,512 INFO L138 BoogieDeclarations]: Found implementation of procedure can_fail_allocator [2021-12-16 03:21:53,512 INFO L130 BoogieDeclarations]: Found specification of procedure __CPROVER_overflow_mult [2021-12-16 03:21:53,512 INFO L138 BoogieDeclarations]: Found implementation of procedure __CPROVER_overflow_mult [2021-12-16 03:21:53,512 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2021-12-16 03:21:53,512 INFO L130 BoogieDeclarations]: Found specification of procedure memset_impl [2021-12-16 03:21:53,513 INFO L138 BoogieDeclarations]: Found implementation of procedure memset_impl [2021-12-16 03:21:53,513 INFO L130 BoogieDeclarations]: Found specification of procedure my_memset [2021-12-16 03:21:53,513 INFO L138 BoogieDeclarations]: Found implementation of procedure my_memset [2021-12-16 03:21:53,513 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-16 03:21:53,802 INFO L236 CfgBuilder]: Building ICFG [2021-12-16 03:21:53,803 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-16 03:21:54,228 INFO L277 CfgBuilder]: Performing block encoding [2021-12-16 03:21:54,232 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-16 03:21:54,232 INFO L301 CfgBuilder]: Removed 6 assume(true) statements. [2021-12-16 03:21:54,233 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.12 03:21:54 BoogieIcfgContainer [2021-12-16 03:21:54,234 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-16 03:21:54,235 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-16 03:21:54,235 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-16 03:21:54,237 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-16 03:21:54,237 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.12 03:21:51" (1/3) ... [2021-12-16 03:21:54,237 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ec5cede and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.12 03:21:54, skipping insertion in model container [2021-12-16 03:21:54,238 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 03:21:53" (2/3) ... [2021-12-16 03:21:54,238 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ec5cede and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.12 03:21:54, skipping insertion in model container [2021-12-16 03:21:54,238 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.12 03:21:54" (3/3) ... [2021-12-16 03:21:54,239 INFO L111 eAbstractionObserver]: Analyzing ICFG aws_priority_queue_init_dynamic_harness-1.i [2021-12-16 03:21:54,242 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-16 03:21:54,242 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-12-16 03:21:54,271 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-16 03:21:54,275 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 [2021-12-16 03:21:54,276 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-12-16 03:21:54,288 INFO L276 IsEmpty]: Start isEmpty. Operand has 205 states, 133 states have (on average 1.255639097744361) internal successors, (167), 133 states have internal predecessors, (167), 56 states have call successors, (56), 16 states have call predecessors, (56), 16 states have return successors, (56), 56 states have call predecessors, (56), 56 states have call successors, (56) [2021-12-16 03:21:54,294 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2021-12-16 03:21:54,294 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 03:21:54,295 INFO L514 BasicCegarLoop]: trace histogram [10, 10, 10, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 03:21:54,295 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-16 03:21:54,298 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 03:21:54,299 INFO L85 PathProgramCache]: Analyzing trace with hash -1293047729, now seen corresponding path program 1 times [2021-12-16 03:21:54,304 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 03:21:54,304 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1709778507] [2021-12-16 03:21:54,305 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:21:54,305 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 03:21:54,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:21:54,683 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-16 03:21:54,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:21:54,699 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-16 03:21:54,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:21:54,710 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-16 03:21:54,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:21:54,724 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2021-12-16 03:21:54,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:21:54,734 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2021-12-16 03:21:54,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:21:54,761 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2021-12-16 03:21:54,770 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 03:21:54,771 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1709778507] [2021-12-16 03:21:54,771 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2021-12-16 03:21:54,771 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1274889709] [2021-12-16 03:21:54,771 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:21:54,771 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:21:54,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:21:54,773 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) [2021-12-16 03:21:54,790 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-12-16 03:21:55,161 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:21:55,170 INFO L263 TraceCheckSpWp]: Trace formula consists of 2214 conjuncts, 1 conjunts are in the unsatisfiable core [2021-12-16 03:21:55,176 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 03:21:55,344 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 18 proven. 0 refuted. 0 times theorem prover too weak. 174 trivial. 0 not checked. [2021-12-16 03:21:55,344 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 03:21:55,344 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1274889709] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 03:21:55,345 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 03:21:55,345 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-16 03:21:55,346 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1406458685] [2021-12-16 03:21:55,347 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 03:21:55,349 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-12-16 03:21:55,350 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 03:21:55,365 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-12-16 03:21:55,365 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-16 03:21:55,367 INFO L87 Difference]: Start difference. First operand has 205 states, 133 states have (on average 1.255639097744361) internal successors, (167), 133 states have internal predecessors, (167), 56 states have call successors, (56), 16 states have call predecessors, (56), 16 states have return successors, (56), 56 states have call predecessors, (56), 56 states have call successors, (56) Second operand has 2 states, 2 states have (on average 20.0) internal successors, (40), 2 states have internal predecessors, (40), 2 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 2 states have call predecessors, (18), 2 states have call successors, (18) [2021-12-16 03:21:55,394 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 03:21:55,394 INFO L93 Difference]: Finished difference Result 401 states and 585 transitions. [2021-12-16 03:21:55,395 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-12-16 03:21:55,396 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 20.0) internal successors, (40), 2 states have internal predecessors, (40), 2 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 2 states have call predecessors, (18), 2 states have call successors, (18) Word has length 112 [2021-12-16 03:21:55,397 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 03:21:55,402 INFO L225 Difference]: With dead ends: 401 [2021-12-16 03:21:55,403 INFO L226 Difference]: Without dead ends: 198 [2021-12-16 03:21:55,406 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 125 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-16 03:21:55,408 INFO L933 BasicCegarLoop]: 271 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 271 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-16 03:21:55,409 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 271 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-16 03:21:55,421 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 198 states. [2021-12-16 03:21:55,440 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 198 to 198. [2021-12-16 03:21:55,441 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 198 states, 125 states have (on average 1.224) internal successors, (153), 127 states have internal predecessors, (153), 56 states have call successors, (56), 16 states have call predecessors, (56), 16 states have return successors, (54), 54 states have call predecessors, (54), 54 states have call successors, (54) [2021-12-16 03:21:55,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 198 states to 198 states and 263 transitions. [2021-12-16 03:21:55,445 INFO L78 Accepts]: Start accepts. Automaton has 198 states and 263 transitions. Word has length 112 [2021-12-16 03:21:55,445 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 03:21:55,446 INFO L470 AbstractCegarLoop]: Abstraction has 198 states and 263 transitions. [2021-12-16 03:21:55,446 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 20.0) internal successors, (40), 2 states have internal predecessors, (40), 2 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 2 states have call predecessors, (18), 2 states have call successors, (18) [2021-12-16 03:21:55,446 INFO L276 IsEmpty]: Start isEmpty. Operand 198 states and 263 transitions. [2021-12-16 03:21:55,448 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2021-12-16 03:21:55,448 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 03:21:55,448 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 03:21:55,471 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-12-16 03:21:55,668 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2021-12-16 03:21:55,669 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-16 03:21:55,669 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 03:21:55,669 INFO L85 PathProgramCache]: Analyzing trace with hash -1403140028, now seen corresponding path program 1 times [2021-12-16 03:21:55,669 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 03:21:55,669 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [175126468] [2021-12-16 03:21:55,670 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:21:55,670 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 03:21:55,726 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-16 03:21:55,726 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1961458654] [2021-12-16 03:21:55,727 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:21:55,727 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:21:55,727 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:21:55,728 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) [2021-12-16 03:21:55,730 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-12-16 03:21:56,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:21:56,199 INFO L263 TraceCheckSpWp]: Trace formula consists of 2368 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-16 03:21:56,203 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 03:21:56,393 INFO L134 CoverageAnalysis]: Checked inductivity of 287 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 284 trivial. 0 not checked. [2021-12-16 03:21:56,393 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 03:21:56,393 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 03:21:56,393 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [175126468] [2021-12-16 03:21:56,393 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-16 03:21:56,393 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1961458654] [2021-12-16 03:21:56,393 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1961458654] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 03:21:56,393 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 03:21:56,394 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-16 03:21:56,394 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [341989195] [2021-12-16 03:21:56,394 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 03:21:56,396 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-16 03:21:56,396 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 03:21:56,397 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-16 03:21:56,397 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-16 03:21:56,398 INFO L87 Difference]: Start difference. First operand 198 states and 263 transitions. Second operand has 5 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 2 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 3 states have call predecessors, (22), 2 states have call successors, (22) [2021-12-16 03:21:56,461 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 03:21:56,461 INFO L93 Difference]: Finished difference Result 302 states and 404 transitions. [2021-12-16 03:21:56,470 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-16 03:21:56,470 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 2 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 3 states have call predecessors, (22), 2 states have call successors, (22) Word has length 146 [2021-12-16 03:21:56,473 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 03:21:56,476 INFO L225 Difference]: With dead ends: 302 [2021-12-16 03:21:56,477 INFO L226 Difference]: Without dead ends: 203 [2021-12-16 03:21:56,478 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 142 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2021-12-16 03:21:56,479 INFO L933 BasicCegarLoop]: 260 mSDtfsCounter, 2 mSDsluCounter, 775 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1035 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-16 03:21:56,479 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1035 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-16 03:21:56,480 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2021-12-16 03:21:56,491 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 203. [2021-12-16 03:21:56,492 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 203 states, 129 states have (on average 1.2170542635658914) internal successors, (157), 131 states have internal predecessors, (157), 56 states have call successors, (56), 16 states have call predecessors, (56), 17 states have return successors, (57), 55 states have call predecessors, (57), 54 states have call successors, (57) [2021-12-16 03:21:56,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 270 transitions. [2021-12-16 03:21:56,493 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 270 transitions. Word has length 146 [2021-12-16 03:21:56,494 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 03:21:56,494 INFO L470 AbstractCegarLoop]: Abstraction has 203 states and 270 transitions. [2021-12-16 03:21:56,494 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 2 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 3 states have call predecessors, (22), 2 states have call successors, (22) [2021-12-16 03:21:56,494 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 270 transitions. [2021-12-16 03:21:56,495 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 148 [2021-12-16 03:21:56,496 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 03:21:56,496 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 03:21:56,522 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-12-16 03:21:56,719 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,SelfDestructingSolverStorable1 [2021-12-16 03:21:56,719 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-16 03:21:56,720 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 03:21:56,720 INFO L85 PathProgramCache]: Analyzing trace with hash 494695836, now seen corresponding path program 1 times [2021-12-16 03:21:56,720 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 03:21:56,720 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1094660307] [2021-12-16 03:21:56,720 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:21:56,720 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 03:21:56,766 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-16 03:21:56,766 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [851204454] [2021-12-16 03:21:56,767 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:21:56,767 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:21:56,767 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:21:56,768 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) [2021-12-16 03:21:56,804 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-12-16 03:21:57,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:21:57,141 INFO L263 TraceCheckSpWp]: Trace formula consists of 2388 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-16 03:21:57,145 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 03:21:57,444 INFO L134 CoverageAnalysis]: Checked inductivity of 293 backedges. 6 proven. 30 refuted. 0 times theorem prover too weak. 257 trivial. 0 not checked. [2021-12-16 03:21:57,444 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 03:21:57,782 INFO L134 CoverageAnalysis]: Checked inductivity of 293 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 293 trivial. 0 not checked. [2021-12-16 03:21:57,782 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 03:21:57,782 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1094660307] [2021-12-16 03:21:57,782 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-16 03:21:57,782 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [851204454] [2021-12-16 03:21:57,783 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [851204454] provided 1 perfect and 1 imperfect interpolant sequences [2021-12-16 03:21:57,783 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-16 03:21:57,783 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 12 [2021-12-16 03:21:57,783 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1019858052] [2021-12-16 03:21:57,783 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 03:21:57,784 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-16 03:21:57,784 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 03:21:57,784 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-16 03:21:57,785 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=109, Unknown=0, NotChecked=0, Total=132 [2021-12-16 03:21:57,785 INFO L87 Difference]: Start difference. First operand 203 states and 270 transitions. Second operand has 5 states, 4 states have (on average 11.5) internal successors, (46), 4 states have internal predecessors, (46), 2 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (22), 1 states have call predecessors, (22), 1 states have call successors, (22) [2021-12-16 03:21:57,835 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 03:21:57,835 INFO L93 Difference]: Finished difference Result 211 states and 278 transitions. [2021-12-16 03:21:57,835 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-16 03:21:57,836 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 11.5) internal successors, (46), 4 states have internal predecessors, (46), 2 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (22), 1 states have call predecessors, (22), 1 states have call successors, (22) Word has length 147 [2021-12-16 03:21:57,836 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 03:21:57,838 INFO L225 Difference]: With dead ends: 211 [2021-12-16 03:21:57,838 INFO L226 Difference]: Without dead ends: 209 [2021-12-16 03:21:57,838 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 293 GetRequests, 282 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2021-12-16 03:21:57,839 INFO L933 BasicCegarLoop]: 264 mSDtfsCounter, 4 mSDsluCounter, 767 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 1031 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-16 03:21:57,839 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 1031 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-16 03:21:57,855 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2021-12-16 03:21:57,864 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 208. [2021-12-16 03:21:57,865 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 208 states, 132 states have (on average 1.2121212121212122) internal successors, (160), 135 states have internal predecessors, (160), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-16 03:21:57,866 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 208 states to 208 states and 275 transitions. [2021-12-16 03:21:57,866 INFO L78 Accepts]: Start accepts. Automaton has 208 states and 275 transitions. Word has length 147 [2021-12-16 03:21:57,867 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 03:21:57,867 INFO L470 AbstractCegarLoop]: Abstraction has 208 states and 275 transitions. [2021-12-16 03:21:57,867 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 11.5) internal successors, (46), 4 states have internal predecessors, (46), 2 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (22), 1 states have call predecessors, (22), 1 states have call successors, (22) [2021-12-16 03:21:57,867 INFO L276 IsEmpty]: Start isEmpty. Operand 208 states and 275 transitions. [2021-12-16 03:21:57,869 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 148 [2021-12-16 03:21:57,880 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 03:21:57,880 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 03:21:57,909 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2021-12-16 03:21:58,095 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:21:58,095 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-16 03:21:58,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 03:21:58,096 INFO L85 PathProgramCache]: Analyzing trace with hash 496542878, now seen corresponding path program 1 times [2021-12-16 03:21:58,097 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 03:21:58,097 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [918699565] [2021-12-16 03:21:58,097 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:21:58,097 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 03:21:58,158 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-16 03:21:58,159 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [106161571] [2021-12-16 03:21:58,159 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:21:58,159 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:21:58,159 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:21:58,160 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) [2021-12-16 03:21:58,161 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-12-16 03:21:58,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:21:58,539 INFO L263 TraceCheckSpWp]: Trace formula consists of 2393 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-16 03:21:58,542 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 03:21:58,822 INFO L134 CoverageAnalysis]: Checked inductivity of 293 backedges. 154 proven. 0 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2021-12-16 03:21:58,823 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 03:21:58,823 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 03:21:58,823 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [918699565] [2021-12-16 03:21:58,823 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-16 03:21:58,823 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [106161571] [2021-12-16 03:21:58,824 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [106161571] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 03:21:58,824 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 03:21:58,824 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2021-12-16 03:21:58,824 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [610267032] [2021-12-16 03:21:58,824 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 03:21:58,825 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-16 03:21:58,825 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 03:21:58,825 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-16 03:21:58,825 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-12-16 03:21:58,826 INFO L87 Difference]: Start difference. First operand 208 states and 275 transitions. Second operand has 6 states, 5 states have (on average 12.8) internal successors, (64), 6 states have internal predecessors, (64), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) [2021-12-16 03:21:58,877 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 03:21:58,877 INFO L93 Difference]: Finished difference Result 401 states and 523 transitions. [2021-12-16 03:21:58,878 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-16 03:21:58,878 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 12.8) internal successors, (64), 6 states have internal predecessors, (64), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) Word has length 147 [2021-12-16 03:21:58,878 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 03:21:58,880 INFO L225 Difference]: With dead ends: 401 [2021-12-16 03:21:58,880 INFO L226 Difference]: Without dead ends: 208 [2021-12-16 03:21:58,880 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 142 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2021-12-16 03:21:58,881 INFO L933 BasicCegarLoop]: 256 mSDtfsCounter, 13 mSDsluCounter, 1007 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 1263 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-16 03:21:58,881 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 1263 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-16 03:21:58,882 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 208 states. [2021-12-16 03:21:58,889 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 208 to 208. [2021-12-16 03:21:58,889 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 208 states, 132 states have (on average 1.2045454545454546) internal successors, (159), 135 states have internal predecessors, (159), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-16 03:21:58,890 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 208 states to 208 states and 274 transitions. [2021-12-16 03:21:58,890 INFO L78 Accepts]: Start accepts. Automaton has 208 states and 274 transitions. Word has length 147 [2021-12-16 03:21:58,891 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 03:21:58,891 INFO L470 AbstractCegarLoop]: Abstraction has 208 states and 274 transitions. [2021-12-16 03:21:58,891 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 12.8) internal successors, (64), 6 states have internal predecessors, (64), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) [2021-12-16 03:21:58,891 INFO L276 IsEmpty]: Start isEmpty. Operand 208 states and 274 transitions. [2021-12-16 03:21:58,892 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 150 [2021-12-16 03:21:58,892 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 03:21:58,893 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 03:21:58,919 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-12-16 03:21:59,108 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:21:59,108 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-16 03:21:59,108 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 03:21:59,108 INFO L85 PathProgramCache]: Analyzing trace with hash -50417486, now seen corresponding path program 1 times [2021-12-16 03:21:59,108 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 03:21:59,108 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1233695205] [2021-12-16 03:21:59,108 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:21:59,108 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 03:21:59,159 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-16 03:21:59,160 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [174142765] [2021-12-16 03:21:59,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:21:59,160 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:21:59,160 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:21:59,161 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) [2021-12-16 03:21:59,162 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-12-16 03:21:59,558 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:21:59,568 INFO L263 TraceCheckSpWp]: Trace formula consists of 2407 conjuncts, 22 conjunts are in the unsatisfiable core [2021-12-16 03:21:59,571 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 03:21:59,814 INFO L134 CoverageAnalysis]: Checked inductivity of 294 backedges. 15 proven. 7 refuted. 0 times theorem prover too weak. 272 trivial. 0 not checked. [2021-12-16 03:21:59,815 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 03:22:00,174 INFO L134 CoverageAnalysis]: Checked inductivity of 294 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 284 trivial. 0 not checked. [2021-12-16 03:22:00,174 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 03:22:00,174 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1233695205] [2021-12-16 03:22:00,174 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-16 03:22:00,175 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [174142765] [2021-12-16 03:22:00,175 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [174142765] provided 1 perfect and 1 imperfect interpolant sequences [2021-12-16 03:22:00,175 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-16 03:22:00,175 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [9] total 13 [2021-12-16 03:22:00,175 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1811931164] [2021-12-16 03:22:00,175 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 03:22:00,175 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-16 03:22:00,175 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 03:22:00,176 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-16 03:22:00,176 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2021-12-16 03:22:00,176 INFO L87 Difference]: Start difference. First operand 208 states and 274 transitions. Second operand has 7 states, 6 states have (on average 9.166666666666666) internal successors, (55), 7 states have internal predecessors, (55), 4 states have call successors, (25), 2 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2021-12-16 03:22:00,219 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 03:22:00,219 INFO L93 Difference]: Finished difference Result 402 states and 523 transitions. [2021-12-16 03:22:00,219 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-16 03:22:00,219 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 9.166666666666666) internal successors, (55), 7 states have internal predecessors, (55), 4 states have call successors, (25), 2 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 149 [2021-12-16 03:22:00,220 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 03:22:00,220 INFO L225 Difference]: With dead ends: 402 [2021-12-16 03:22:00,221 INFO L226 Difference]: Without dead ends: 209 [2021-12-16 03:22:00,221 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 296 GetRequests, 285 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2021-12-16 03:22:00,222 INFO L933 BasicCegarLoop]: 255 mSDtfsCounter, 17 mSDsluCounter, 1006 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 1261 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-16 03:22:00,222 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 1261 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-16 03:22:00,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2021-12-16 03:22:00,228 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 209. [2021-12-16 03:22:00,234 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 209 states, 133 states have (on average 1.2030075187969924) internal successors, (160), 136 states have internal predecessors, (160), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-16 03:22:00,235 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 209 states to 209 states and 275 transitions. [2021-12-16 03:22:00,235 INFO L78 Accepts]: Start accepts. Automaton has 209 states and 275 transitions. Word has length 149 [2021-12-16 03:22:00,236 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 03:22:00,236 INFO L470 AbstractCegarLoop]: Abstraction has 209 states and 275 transitions. [2021-12-16 03:22:00,236 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 9.166666666666666) internal successors, (55), 7 states have internal predecessors, (55), 4 states have call successors, (25), 2 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2021-12-16 03:22:00,236 INFO L276 IsEmpty]: Start isEmpty. Operand 209 states and 275 transitions. [2021-12-16 03:22:00,237 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 154 [2021-12-16 03:22:00,237 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 03:22:00,237 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 03:22:00,277 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-12-16 03:22:00,451 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:22:00,452 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-16 03:22:00,452 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 03:22:00,452 INFO L85 PathProgramCache]: Analyzing trace with hash 2024331122, now seen corresponding path program 1 times [2021-12-16 03:22:00,452 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 03:22:00,452 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [632469336] [2021-12-16 03:22:00,452 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:22:00,452 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 03:22:00,504 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-16 03:22:00,504 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1536898539] [2021-12-16 03:22:00,504 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:22:00,504 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:22:00,504 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:22:00,505 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) [2021-12-16 03:22:00,506 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-12-16 03:22:00,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 03:22:00,908 INFO L263 TraceCheckSpWp]: Trace formula consists of 2445 conjuncts, 26 conjunts are in the unsatisfiable core [2021-12-16 03:22:00,911 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 03:22:01,225 INFO L134 CoverageAnalysis]: Checked inductivity of 300 backedges. 159 proven. 1 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2021-12-16 03:22:01,225 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 03:22:01,714 INFO L134 CoverageAnalysis]: Checked inductivity of 300 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 285 trivial. 0 not checked. [2021-12-16 03:22:01,714 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 03:22:01,714 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [632469336] [2021-12-16 03:22:01,714 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-16 03:22:01,714 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1536898539] [2021-12-16 03:22:01,714 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1536898539] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 03:22:01,715 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-16 03:22:01,715 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2021-12-16 03:22:01,715 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1717008845] [2021-12-16 03:22:01,715 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-16 03:22:01,715 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2021-12-16 03:22:01,715 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 03:22:01,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-12-16 03:22:01,716 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2021-12-16 03:22:01,716 INFO L87 Difference]: Start difference. First operand 209 states and 275 transitions. Second operand has 13 states, 11 states have (on average 8.0) internal successors, (88), 13 states have internal predecessors, (88), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-16 03:22:01,812 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 03:22:01,813 INFO L93 Difference]: Finished difference Result 406 states and 527 transitions. [2021-12-16 03:22:01,813 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-16 03:22:01,813 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 8.0) internal successors, (88), 13 states have internal predecessors, (88), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) Word has length 153 [2021-12-16 03:22:01,813 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 03:22:01,814 INFO L225 Difference]: With dead ends: 406 [2021-12-16 03:22:01,814 INFO L226 Difference]: Without dead ends: 212 [2021-12-16 03:22:01,815 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 307 GetRequests, 292 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2021-12-16 03:22:01,815 INFO L933 BasicCegarLoop]: 255 mSDtfsCounter, 25 mSDsluCounter, 1758 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 2013 SdHoareTripleChecker+Invalid, 79 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-16 03:22:01,816 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 2013 Invalid, 79 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-16 03:22:01,816 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 212 states. [2021-12-16 03:22:01,820 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 212 to 211. [2021-12-16 03:22:01,820 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 211 states, 135 states have (on average 1.2) internal successors, (162), 138 states have internal predecessors, (162), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-16 03:22:01,821 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 211 states to 211 states and 277 transitions. [2021-12-16 03:22:01,822 INFO L78 Accepts]: Start accepts. Automaton has 211 states and 277 transitions. Word has length 153 [2021-12-16 03:22:01,822 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 03:22:01,822 INFO L470 AbstractCegarLoop]: Abstraction has 211 states and 277 transitions. [2021-12-16 03:22:01,822 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 8.0) internal successors, (88), 13 states have internal predecessors, (88), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-16 03:22:01,822 INFO L276 IsEmpty]: Start isEmpty. Operand 211 states and 277 transitions. [2021-12-16 03:22:01,823 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 158 [2021-12-16 03:22:01,823 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 03:22:01,823 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 03:22:01,861 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-12-16 03:22:02,040 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:22:02,041 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-16 03:22:02,041 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 03:22:02,041 INFO L85 PathProgramCache]: Analyzing trace with hash 1553173810, now seen corresponding path program 2 times [2021-12-16 03:22:02,042 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 03:22:02,042 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1147323523] [2021-12-16 03:22:02,042 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:22:02,042 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 03:22:02,096 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-16 03:22:02,102 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [185049897] [2021-12-16 03:22:02,102 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-16 03:22:02,102 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:22:02,102 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:22:02,116 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) [2021-12-16 03:22:02,117 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-12-16 03:22:02,772 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-16 03:22:02,772 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-16 03:22:02,784 INFO L263 TraceCheckSpWp]: Trace formula consists of 2483 conjuncts, 30 conjunts are in the unsatisfiable core [2021-12-16 03:22:02,787 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 03:22:03,063 INFO L134 CoverageAnalysis]: Checked inductivity of 314 backedges. 167 proven. 4 refuted. 0 times theorem prover too weak. 143 trivial. 0 not checked. [2021-12-16 03:22:03,063 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 03:22:03,563 INFO L134 CoverageAnalysis]: Checked inductivity of 314 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2021-12-16 03:22:03,563 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 03:22:03,563 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1147323523] [2021-12-16 03:22:03,564 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-16 03:22:03,564 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [185049897] [2021-12-16 03:22:03,564 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [185049897] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 03:22:03,564 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-16 03:22:03,564 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2021-12-16 03:22:03,564 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2141219383] [2021-12-16 03:22:03,564 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-16 03:22:03,564 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2021-12-16 03:22:03,564 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 03:22:03,565 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2021-12-16 03:22:03,565 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2021-12-16 03:22:03,565 INFO L87 Difference]: Start difference. First operand 211 states and 277 transitions. Second operand has 17 states, 15 states have (on average 6.133333333333334) internal successors, (92), 17 states have internal predecessors, (92), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-16 03:22:03,766 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 03:22:03,766 INFO L93 Difference]: Finished difference Result 410 states and 531 transitions. [2021-12-16 03:22:03,766 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-12-16 03:22:03,767 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 6.133333333333334) internal successors, (92), 17 states have internal predecessors, (92), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) Word has length 157 [2021-12-16 03:22:03,767 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 03:22:03,768 INFO L225 Difference]: With dead ends: 410 [2021-12-16 03:22:03,768 INFO L226 Difference]: Without dead ends: 214 [2021-12-16 03:22:03,769 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 317 GetRequests, 297 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=97, Invalid=365, Unknown=0, NotChecked=0, Total=462 [2021-12-16 03:22:03,769 INFO L933 BasicCegarLoop]: 255 mSDtfsCounter, 42 mSDsluCounter, 2264 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 2519 SdHoareTripleChecker+Invalid, 139 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-16 03:22:03,769 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 2519 Invalid, 139 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-16 03:22:03,770 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 214 states. [2021-12-16 03:22:03,774 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 214 to 213. [2021-12-16 03:22:03,774 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 213 states, 137 states have (on average 1.197080291970803) internal successors, (164), 140 states have internal predecessors, (164), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-16 03:22:03,775 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 279 transitions. [2021-12-16 03:22:03,776 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 279 transitions. Word has length 157 [2021-12-16 03:22:03,776 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 03:22:03,776 INFO L470 AbstractCegarLoop]: Abstraction has 213 states and 279 transitions. [2021-12-16 03:22:03,777 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 6.133333333333334) internal successors, (92), 17 states have internal predecessors, (92), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-16 03:22:03,777 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 279 transitions. [2021-12-16 03:22:03,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 162 [2021-12-16 03:22:03,778 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 03:22:03,779 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 6, 6, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 03:22:03,803 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-12-16 03:22:04,000 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:22:04,001 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-16 03:22:04,001 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 03:22:04,001 INFO L85 PathProgramCache]: Analyzing trace with hash 1663013362, now seen corresponding path program 3 times [2021-12-16 03:22:04,001 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 03:22:04,001 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [204081913] [2021-12-16 03:22:04,001 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:22:04,001 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 03:22:04,054 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-16 03:22:04,054 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1066086627] [2021-12-16 03:22:04,054 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-16 03:22:04,054 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:22:04,055 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:22:04,059 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) [2021-12-16 03:22:04,060 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-12-16 03:22:06,111 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2021-12-16 03:22:06,111 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-16 03:22:06,125 INFO L263 TraceCheckSpWp]: Trace formula consists of 2109 conjuncts, 86 conjunts are in the unsatisfiable core [2021-12-16 03:22:06,129 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 03:22:06,474 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 40 [2021-12-16 03:22:06,480 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 2 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 43 [2021-12-16 03:22:06,508 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-12-16 03:22:06,520 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 58 treesize of output 37 [2021-12-16 03:22:06,818 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 49 proven. 9 refuted. 0 times theorem prover too weak. 278 trivial. 0 not checked. [2021-12-16 03:22:06,818 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 03:22:06,971 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 03:22:06,972 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [204081913] [2021-12-16 03:22:06,972 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-16 03:22:06,972 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1066086627] [2021-12-16 03:22:06,972 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1066086627] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-16 03:22:06,973 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-16 03:22:06,973 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2021-12-16 03:22:06,973 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [902172049] [2021-12-16 03:22:06,973 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-16 03:22:06,973 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2021-12-16 03:22:06,974 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 03:22:06,974 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-12-16 03:22:06,974 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2021-12-16 03:22:06,975 INFO L87 Difference]: Start difference. First operand 213 states and 279 transitions. Second operand has 11 states, 10 states have (on average 7.1) internal successors, (71), 11 states have internal predecessors, (71), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) [2021-12-16 03:22:07,499 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 03:22:07,499 INFO L93 Difference]: Finished difference Result 414 states and 535 transitions. [2021-12-16 03:22:07,499 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-12-16 03:22:07,500 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 7.1) internal successors, (71), 11 states have internal predecessors, (71), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) Word has length 161 [2021-12-16 03:22:07,500 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 03:22:07,502 INFO L225 Difference]: With dead ends: 414 [2021-12-16 03:22:07,502 INFO L226 Difference]: Without dead ends: 216 [2021-12-16 03:22:07,503 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 174 GetRequests, 153 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=59, Invalid=403, Unknown=0, NotChecked=0, Total=462 [2021-12-16 03:22:07,503 INFO L933 BasicCegarLoop]: 254 mSDtfsCounter, 20 mSDsluCounter, 2172 mSDsCounter, 0 mSdLazyCounter, 227 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 2426 SdHoareTripleChecker+Invalid, 234 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 227 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-16 03:22:07,503 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 2426 Invalid, 234 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 227 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-12-16 03:22:07,504 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 216 states. [2021-12-16 03:22:07,511 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 216 to 215. [2021-12-16 03:22:07,512 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 215 states, 139 states have (on average 1.1942446043165467) internal successors, (166), 142 states have internal predecessors, (166), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-16 03:22:07,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 281 transitions. [2021-12-16 03:22:07,513 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 281 transitions. Word has length 161 [2021-12-16 03:22:07,513 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 03:22:07,514 INFO L470 AbstractCegarLoop]: Abstraction has 215 states and 281 transitions. [2021-12-16 03:22:07,514 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 7.1) internal successors, (71), 11 states have internal predecessors, (71), 4 states have call successors, (26), 2 states have call predecessors, (26), 4 states have return successors, (25), 4 states have call predecessors, (25), 4 states have call successors, (25) [2021-12-16 03:22:07,514 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 281 transitions. [2021-12-16 03:22:07,515 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 166 [2021-12-16 03:22:07,516 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 03:22:07,517 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 8, 8, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 03:22:07,533 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2021-12-16 03:22:07,728 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,SelfDestructingSolverStorable7 [2021-12-16 03:22:07,728 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-16 03:22:07,729 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 03:22:07,729 INFO L85 PathProgramCache]: Analyzing trace with hash -650271310, now seen corresponding path program 4 times [2021-12-16 03:22:07,729 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 03:22:07,729 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [781716195] [2021-12-16 03:22:07,729 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:22:07,729 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 03:22:07,770 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-16 03:22:07,771 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [88628757] [2021-12-16 03:22:07,771 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-16 03:22:07,771 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:22:07,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:22:07,772 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) [2021-12-16 03:22:07,788 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2021-12-16 03:22:08,245 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-16 03:22:08,246 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-16 03:22:08,255 INFO L263 TraceCheckSpWp]: Trace formula consists of 2559 conjuncts, 28 conjunts are in the unsatisfiable core [2021-12-16 03:22:08,257 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 03:22:08,574 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 64 proven. 16 refuted. 0 times theorem prover too weak. 286 trivial. 0 not checked. [2021-12-16 03:22:08,574 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 03:22:09,132 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 50 proven. 16 refuted. 0 times theorem prover too weak. 300 trivial. 0 not checked. [2021-12-16 03:22:09,132 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 03:22:09,132 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [781716195] [2021-12-16 03:22:09,132 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-16 03:22:09,132 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [88628757] [2021-12-16 03:22:09,132 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [88628757] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 03:22:09,132 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-16 03:22:09,132 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 19 [2021-12-16 03:22:09,132 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1536861041] [2021-12-16 03:22:09,133 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-16 03:22:09,133 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2021-12-16 03:22:09,133 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 03:22:09,133 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2021-12-16 03:22:09,133 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=271, Unknown=0, NotChecked=0, Total=342 [2021-12-16 03:22:09,134 INFO L87 Difference]: Start difference. First operand 215 states and 281 transitions. Second operand has 19 states, 17 states have (on average 5.117647058823529) internal successors, (87), 19 states have internal predecessors, (87), 6 states have call successors, (30), 2 states have call predecessors, (30), 5 states have return successors, (31), 6 states have call predecessors, (31), 6 states have call successors, (31) [2021-12-16 03:22:09,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 03:22:09,310 INFO L93 Difference]: Finished difference Result 418 states and 539 transitions. [2021-12-16 03:22:09,311 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-12-16 03:22:09,311 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 5.117647058823529) internal successors, (87), 19 states have internal predecessors, (87), 6 states have call successors, (30), 2 states have call predecessors, (30), 5 states have return successors, (31), 6 states have call predecessors, (31), 6 states have call successors, (31) Word has length 165 [2021-12-16 03:22:09,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 03:22:09,312 INFO L225 Difference]: With dead ends: 418 [2021-12-16 03:22:09,312 INFO L226 Difference]: Without dead ends: 218 [2021-12-16 03:22:09,313 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 331 GetRequests, 311 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=99, Invalid=363, Unknown=0, NotChecked=0, Total=462 [2021-12-16 03:22:09,313 INFO L933 BasicCegarLoop]: 255 mSDtfsCounter, 46 mSDsluCounter, 2022 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 2277 SdHoareTripleChecker+Invalid, 173 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-16 03:22:09,314 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [48 Valid, 2277 Invalid, 173 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-16 03:22:09,314 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2021-12-16 03:22:09,319 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 217. [2021-12-16 03:22:09,319 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 141 states have (on average 1.1914893617021276) internal successors, (168), 144 states have internal predecessors, (168), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-16 03:22:09,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 283 transitions. [2021-12-16 03:22:09,320 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 283 transitions. Word has length 165 [2021-12-16 03:22:09,321 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 03:22:09,321 INFO L470 AbstractCegarLoop]: Abstraction has 217 states and 283 transitions. [2021-12-16 03:22:09,321 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 5.117647058823529) internal successors, (87), 19 states have internal predecessors, (87), 6 states have call successors, (30), 2 states have call predecessors, (30), 5 states have return successors, (31), 6 states have call predecessors, (31), 6 states have call successors, (31) [2021-12-16 03:22:09,321 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 283 transitions. [2021-12-16 03:22:09,322 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 170 [2021-12-16 03:22:09,322 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 03:22:09,322 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 10, 10, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 03:22:09,348 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2021-12-16 03:22:09,539 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:22:09,539 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-16 03:22:09,540 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 03:22:09,540 INFO L85 PathProgramCache]: Analyzing trace with hash 1517193330, now seen corresponding path program 5 times [2021-12-16 03:22:09,540 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 03:22:09,540 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [658038662] [2021-12-16 03:22:09,540 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:22:09,540 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 03:22:09,604 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-16 03:22:09,604 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1640888328] [2021-12-16 03:22:09,604 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-16 03:22:09,604 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:22:09,605 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:22:09,624 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) [2021-12-16 03:22:09,628 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2021-12-16 03:22:10,418 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2021-12-16 03:22:10,419 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-16 03:22:10,424 INFO L263 TraceCheckSpWp]: Trace formula consists of 462 conjuncts, 22 conjunts are in the unsatisfiable core [2021-12-16 03:22:10,427 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 03:22:10,871 INFO L134 CoverageAnalysis]: Checked inductivity of 404 backedges. 215 proven. 25 refuted. 0 times theorem prover too weak. 164 trivial. 0 not checked. [2021-12-16 03:22:10,871 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 03:22:11,541 INFO L134 CoverageAnalysis]: Checked inductivity of 404 backedges. 0 proven. 95 refuted. 0 times theorem prover too weak. 309 trivial. 0 not checked. [2021-12-16 03:22:11,541 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 03:22:11,541 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [658038662] [2021-12-16 03:22:11,541 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-16 03:22:11,541 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1640888328] [2021-12-16 03:22:11,541 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1640888328] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 03:22:11,541 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-16 03:22:11,541 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2021-12-16 03:22:11,542 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1110488061] [2021-12-16 03:22:11,542 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-16 03:22:11,543 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2021-12-16 03:22:11,543 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 03:22:11,543 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-16 03:22:11,543 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=336, Unknown=0, NotChecked=0, Total=420 [2021-12-16 03:22:11,543 INFO L87 Difference]: Start difference. First operand 217 states and 283 transitions. Second operand has 21 states, 19 states have (on average 5.473684210526316) internal successors, (104), 21 states have internal predecessors, (104), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-16 03:22:11,792 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 03:22:11,793 INFO L93 Difference]: Finished difference Result 422 states and 543 transitions. [2021-12-16 03:22:11,807 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-16 03:22:11,808 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 5.473684210526316) internal successors, (104), 21 states have internal predecessors, (104), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) Word has length 169 [2021-12-16 03:22:11,808 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 03:22:11,809 INFO L225 Difference]: With dead ends: 422 [2021-12-16 03:22:11,809 INFO L226 Difference]: Without dead ends: 220 [2021-12-16 03:22:11,810 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 339 GetRequests, 317 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=114, Invalid=438, Unknown=0, NotChecked=0, Total=552 [2021-12-16 03:22:11,811 INFO L933 BasicCegarLoop]: 255 mSDtfsCounter, 37 mSDsluCounter, 4028 mSDsCounter, 0 mSdLazyCounter, 272 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 4283 SdHoareTripleChecker+Invalid, 291 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 272 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-16 03:22:11,811 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 4283 Invalid, 291 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 272 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-16 03:22:11,812 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2021-12-16 03:22:11,820 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 219. [2021-12-16 03:22:11,821 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 219 states, 143 states have (on average 1.1888111888111887) internal successors, (170), 146 states have internal predecessors, (170), 57 states have call successors, (57), 17 states have call predecessors, (57), 18 states have return successors, (58), 55 states have call predecessors, (58), 55 states have call successors, (58) [2021-12-16 03:22:11,822 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 219 states to 219 states and 285 transitions. [2021-12-16 03:22:11,822 INFO L78 Accepts]: Start accepts. Automaton has 219 states and 285 transitions. Word has length 169 [2021-12-16 03:22:11,823 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 03:22:11,823 INFO L470 AbstractCegarLoop]: Abstraction has 219 states and 285 transitions. [2021-12-16 03:22:11,823 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 5.473684210526316) internal successors, (104), 21 states have internal predecessors, (104), 6 states have call successors, (36), 2 states have call predecessors, (36), 5 states have return successors, (36), 6 states have call predecessors, (36), 6 states have call successors, (36) [2021-12-16 03:22:11,823 INFO L276 IsEmpty]: Start isEmpty. Operand 219 states and 285 transitions. [2021-12-16 03:22:11,825 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 174 [2021-12-16 03:22:11,825 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 03:22:11,825 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 12, 12, 12, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 03:22:11,847 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2021-12-16 03:22:12,032 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,SelfDestructingSolverStorable9 [2021-12-16 03:22:12,033 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-16 03:22:12,034 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 03:22:12,035 INFO L85 PathProgramCache]: Analyzing trace with hash -1933379022, now seen corresponding path program 6 times [2021-12-16 03:22:12,035 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 03:22:12,035 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [627301117] [2021-12-16 03:22:12,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 03:22:12,035 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 03:22:12,097 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-16 03:22:12,097 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [611519150] [2021-12-16 03:22:12,097 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2021-12-16 03:22:12,097 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 03:22:12,097 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 03:22:12,098 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) [2021-12-16 03:22:12,133 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process