./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/verifythis/prefixsum_rec.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3c39aff9 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx12G -Xms1G -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.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/verifythis/prefixsum_rec.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-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(__VERIFIER_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 4f7077bba653370b680c2ff46ec9417a9e7cf514 ........................................................................................................................................................................................................................................................................................... Execution finished normally Using bit-precise analysis Retrying with bit-precise analysis Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx12G -Xms1G -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.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/verifythis/prefixsum_rec.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.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(__VERIFIER_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 4f7077bba653370b680c2ff46ec9417a9e7cf514 ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ Execution finished normally Writing output log to file Ultimate.log Result: ERROR: ExceptionOrErrorResult: AssertionError: Alternating quantifiers not yet supported --- Real Ultimate output --- This is Ultimate 0.1.24-3c39aff [2019-11-27 18:47:19,924 INFO L177 SettingsManager]: Resetting all preferences to default values... [2019-11-27 18:47:19,926 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2019-11-27 18:47:19,939 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2019-11-27 18:47:19,939 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2019-11-27 18:47:19,941 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2019-11-27 18:47:19,942 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2019-11-27 18:47:19,944 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2019-11-27 18:47:19,946 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2019-11-27 18:47:19,948 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2019-11-27 18:47:19,949 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2019-11-27 18:47:19,950 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2019-11-27 18:47:19,950 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2019-11-27 18:47:19,951 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2019-11-27 18:47:19,954 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2019-11-27 18:47:19,955 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2019-11-27 18:47:19,957 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2019-11-27 18:47:19,959 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2019-11-27 18:47:19,962 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2019-11-27 18:47:19,966 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2019-11-27 18:47:19,967 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2019-11-27 18:47:19,969 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2019-11-27 18:47:19,973 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2019-11-27 18:47:19,974 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2019-11-27 18:47:19,977 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2019-11-27 18:47:19,979 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2019-11-27 18:47:19,980 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2019-11-27 18:47:19,981 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2019-11-27 18:47:19,983 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2019-11-27 18:47:19,984 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2019-11-27 18:47:19,985 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2019-11-27 18:47:19,986 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2019-11-27 18:47:19,987 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2019-11-27 18:47:19,988 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2019-11-27 18:47:19,992 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2019-11-27 18:47:19,992 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2019-11-27 18:47:19,994 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2019-11-27 18:47:19,994 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2019-11-27 18:47:19,994 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2019-11-27 18:47:19,998 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2019-11-27 18:47:20,000 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2019-11-27 18:47:20,001 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2019-11-27 18:47:20,023 INFO L113 SettingsManager]: Loading preferences was successful [2019-11-27 18:47:20,024 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2019-11-27 18:47:20,026 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2019-11-27 18:47:20,026 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2019-11-27 18:47:20,026 INFO L138 SettingsManager]: * Use SBE=true [2019-11-27 18:47:20,027 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2019-11-27 18:47:20,027 INFO L138 SettingsManager]: * sizeof long=4 [2019-11-27 18:47:20,027 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2019-11-27 18:47:20,028 INFO L138 SettingsManager]: * sizeof POINTER=4 [2019-11-27 18:47:20,028 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2019-11-27 18:47:20,029 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2019-11-27 18:47:20,030 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2019-11-27 18:47:20,030 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2019-11-27 18:47:20,030 INFO L138 SettingsManager]: * sizeof long double=12 [2019-11-27 18:47:20,031 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2019-11-27 18:47:20,031 INFO L138 SettingsManager]: * Use constant arrays=true [2019-11-27 18:47:20,031 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2019-11-27 18:47:20,031 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2019-11-27 18:47:20,032 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2019-11-27 18:47:20,032 INFO L138 SettingsManager]: * To the following directory=./dump/ [2019-11-27 18:47:20,032 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2019-11-27 18:47:20,032 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-11-27 18:47:20,033 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2019-11-27 18:47:20,033 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2019-11-27 18:47:20,033 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2019-11-27 18:47:20,034 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2019-11-27 18:47:20,034 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2019-11-27 18:47:20,034 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2019-11-27 18:47:20,034 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode 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(__VERIFIER_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 -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 4f7077bba653370b680c2ff46ec9417a9e7cf514 [2019-11-27 18:47:20,332 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2019-11-27 18:47:20,345 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2019-11-27 18:47:20,350 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2019-11-27 18:47:20,351 INFO L271 PluginConnector]: Initializing CDTParser... [2019-11-27 18:47:20,352 INFO L275 PluginConnector]: CDTParser initialized [2019-11-27 18:47:20,353 INFO L428 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/verifythis/prefixsum_rec.c [2019-11-27 18:47:20,415 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2992ef378/f30d8b6891bd4238856e4fccba1cd229/FLAGaf91184d3 [2019-11-27 18:47:20,901 INFO L306 CDTParser]: Found 1 translation units. [2019-11-27 18:47:20,902 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/verifythis/prefixsum_rec.c [2019-11-27 18:47:20,909 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2992ef378/f30d8b6891bd4238856e4fccba1cd229/FLAGaf91184d3 [2019-11-27 18:47:21,242 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2992ef378/f30d8b6891bd4238856e4fccba1cd229 [2019-11-27 18:47:21,246 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2019-11-27 18:47:21,248 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2019-11-27 18:47:21,249 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2019-11-27 18:47:21,249 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2019-11-27 18:47:21,253 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2019-11-27 18:47:21,254 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.11 06:47:21" (1/1) ... [2019-11-27 18:47:21,257 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@66bfba7b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21, skipping insertion in model container [2019-11-27 18:47:21,258 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.11 06:47:21" (1/1) ... [2019-11-27 18:47:21,266 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2019-11-27 18:47:21,287 INFO L178 MainTranslator]: Built tables and reachable declarations [2019-11-27 18:47:21,560 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-27 18:47:21,577 INFO L203 MainTranslator]: Completed pre-run [2019-11-27 18:47:21,655 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-27 18:47:21,673 INFO L208 MainTranslator]: Completed translation [2019-11-27 18:47:21,674 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21 WrapperNode [2019-11-27 18:47:21,674 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2019-11-27 18:47:21,675 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2019-11-27 18:47:21,675 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2019-11-27 18:47:21,676 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2019-11-27 18:47:21,684 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21" (1/1) ... [2019-11-27 18:47:21,696 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21" (1/1) ... [2019-11-27 18:47:21,723 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2019-11-27 18:47:21,723 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2019-11-27 18:47:21,724 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2019-11-27 18:47:21,724 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2019-11-27 18:47:21,732 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21" (1/1) ... [2019-11-27 18:47:21,732 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21" (1/1) ... [2019-11-27 18:47:21,735 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21" (1/1) ... [2019-11-27 18:47:21,735 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21" (1/1) ... [2019-11-27 18:47:21,744 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21" (1/1) ... [2019-11-27 18:47:21,750 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21" (1/1) ... [2019-11-27 18:47:21,752 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21" (1/1) ... [2019-11-27 18:47:21,756 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2019-11-27 18:47:21,756 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2019-11-27 18:47:21,757 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2019-11-27 18:47:21,757 INFO L275 PluginConnector]: RCFGBuilder initialized [2019-11-27 18:47:21,758 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-11-27 18:47:21,814 INFO L130 BoogieDeclarations]: Found specification of procedure downsweep [2019-11-27 18:47:21,815 INFO L138 BoogieDeclarations]: Found implementation of procedure downsweep [2019-11-27 18:47:21,815 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2019-11-27 18:47:21,815 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2019-11-27 18:47:21,816 INFO L130 BoogieDeclarations]: Found specification of procedure upsweep [2019-11-27 18:47:21,816 INFO L138 BoogieDeclarations]: Found implementation of procedure upsweep [2019-11-27 18:47:21,816 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2019-11-27 18:47:21,816 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2019-11-27 18:47:21,816 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2019-11-27 18:47:21,817 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2019-11-27 18:47:22,221 INFO L282 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2019-11-27 18:47:22,222 INFO L287 CfgBuilder]: Removed 17 assume(true) statements. [2019-11-27 18:47:22,223 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 06:47:22 BoogieIcfgContainer [2019-11-27 18:47:22,223 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2019-11-27 18:47:22,224 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2019-11-27 18:47:22,225 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2019-11-27 18:47:22,228 INFO L275 PluginConnector]: TraceAbstraction initialized [2019-11-27 18:47:22,228 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 27.11 06:47:21" (1/3) ... [2019-11-27 18:47:22,229 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1e4c36b4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.11 06:47:22, skipping insertion in model container [2019-11-27 18:47:22,229 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:21" (2/3) ... [2019-11-27 18:47:22,230 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1e4c36b4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.11 06:47:22, skipping insertion in model container [2019-11-27 18:47:22,230 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 06:47:22" (3/3) ... [2019-11-27 18:47:22,232 INFO L109 eAbstractionObserver]: Analyzing ICFG prefixsum_rec.c [2019-11-27 18:47:22,242 INFO L156 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2019-11-27 18:47:22,250 INFO L168 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2019-11-27 18:47:22,262 INFO L249 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2019-11-27 18:47:22,285 INFO L373 AbstractCegarLoop]: Interprodecural is true [2019-11-27 18:47:22,285 INFO L374 AbstractCegarLoop]: Hoare is true [2019-11-27 18:47:22,285 INFO L375 AbstractCegarLoop]: Compute interpolants for FPandBP [2019-11-27 18:47:22,286 INFO L376 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2019-11-27 18:47:22,286 INFO L377 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2019-11-27 18:47:22,286 INFO L378 AbstractCegarLoop]: Difference is false [2019-11-27 18:47:22,286 INFO L379 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2019-11-27 18:47:22,286 INFO L383 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2019-11-27 18:47:22,304 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states. [2019-11-27 18:47:22,310 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2019-11-27 18:47:22,310 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:47:22,311 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-27 18:47:22,311 INFO L410 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:47:22,316 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:47:22,317 INFO L82 PathProgramCache]: Analyzing trace with hash -1360829009, now seen corresponding path program 1 times [2019-11-27 18:47:22,325 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-27 18:47:22,326 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1539667028] [2019-11-27 18:47:22,326 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-27 18:47:22,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-27 18:47:22,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-27 18:47:22,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-27 18:47:22,637 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-27 18:47:22,638 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1539667028] [2019-11-27 18:47:22,639 INFO L220 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-11-27 18:47:22,639 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2019-11-27 18:47:22,641 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [465840307] [2019-11-27 18:47:22,646 INFO L442 AbstractCegarLoop]: Interpolant automaton has 5 states [2019-11-27 18:47:22,646 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-27 18:47:22,661 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2019-11-27 18:47:22,662 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2019-11-27 18:47:22,665 INFO L87 Difference]: Start difference. First operand 36 states. Second operand 5 states. [2019-11-27 18:47:22,834 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-27 18:47:22,834 INFO L93 Difference]: Finished difference Result 72 states and 96 transitions. [2019-11-27 18:47:22,836 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2019-11-27 18:47:22,837 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 24 [2019-11-27 18:47:22,838 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-27 18:47:22,849 INFO L225 Difference]: With dead ends: 72 [2019-11-27 18:47:22,849 INFO L226 Difference]: Without dead ends: 35 [2019-11-27 18:47:22,855 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2019-11-27 18:47:22,876 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2019-11-27 18:47:22,908 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 33. [2019-11-27 18:47:22,909 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2019-11-27 18:47:22,911 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 41 transitions. [2019-11-27 18:47:22,913 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 41 transitions. Word has length 24 [2019-11-27 18:47:22,913 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-27 18:47:22,913 INFO L462 AbstractCegarLoop]: Abstraction has 33 states and 41 transitions. [2019-11-27 18:47:22,913 INFO L463 AbstractCegarLoop]: Interpolant automaton has 5 states. [2019-11-27 18:47:22,913 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 41 transitions. [2019-11-27 18:47:22,916 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2019-11-27 18:47:22,916 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:47:22,916 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-27 18:47:22,917 INFO L410 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:47:22,917 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:47:22,917 INFO L82 PathProgramCache]: Analyzing trace with hash -1965744595, now seen corresponding path program 1 times [2019-11-27 18:47:22,918 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-27 18:47:22,918 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [66375502] [2019-11-27 18:47:22,918 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-27 18:47:22,980 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-27 18:47:23,270 FATAL L? ?]: An unrecoverable error occured during an interaction with an SMT solver: de.uni_freiburg.informatik.ultimate.logic.SMTLIBException: Undeclared function symbol (const Int) at de.uni_freiburg.informatik.ultimate.logic.NoopScript.term(NoopScript.java:478) at de.uni_freiburg.informatik.ultimate.logic.WrapperScript.term(WrapperScript.java:250) at de.uni_freiburg.informatik.ultimate.logic.WrapperScript.term(WrapperScript.java:250) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.SmtUtils.termWithLocalSimplification(SmtUtils.java:1315) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.SmtUtils.termWithLocalSimplification(SmtUtils.java:1196) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.scripttransfer.TermTransferrer.convertApplicationTerm(TermTransferrer.java:182) at de.uni_freiburg.informatik.ultimate.logic.TermTransformer$BuildApplicationTerm.walk(TermTransformer.java:339) at de.uni_freiburg.informatik.ultimate.logic.NonRecursive.run(NonRecursive.java:115) at de.uni_freiburg.informatik.ultimate.logic.NonRecursive.run(NonRecursive.java:106) at de.uni_freiburg.informatik.ultimate.logic.TermTransformer.transform(TermTransformer.java:272) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.NestedInterpolantsBuilder.computePredicates(NestedInterpolantsBuilder.java:573) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.NestedInterpolantsBuilder.(NestedInterpolantsBuilder.java:171) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.InterpolatingTraceCheckCraig.computeInterpolantsRecursive(InterpolatingTraceCheckCraig.java:300) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.InterpolatingTraceCheckCraig.computeInterpolants(InterpolatingTraceCheckCraig.java:202) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.InterpolatingTraceCheckCraig.(InterpolatingTraceCheckCraig.java:107) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleCraig.construct(IpTcStrategyModuleCraig.java:79) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleCraig.construct(IpTcStrategyModuleCraig.java:1) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.isCorrect(IpTcStrategyModuleBase.java:57) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.checkFeasibility(AutomatonFreeRefinementEngine.java:242) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:166) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:75) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:463) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterateInternal(AbstractCegarLoop.java:419) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:368) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopResult.iterate(CegarLoopResult.java:139) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.iterateNew(TraceAbstractionStarter.java:332) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:174) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:126) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:120) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:316) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:55) [2019-11-27 18:47:23,278 INFO L168 Benchmark]: Toolchain (without parser) took 2029.25 ms. Allocated memory was 1.0 GB in the beginning and 1.2 GB in the end (delta: 148.4 MB). Free memory was 960.4 MB in the beginning and 1.1 GB in the end (delta: -93.0 MB). Peak memory consumption was 55.4 MB. Max. memory is 11.5 GB. [2019-11-27 18:47:23,279 INFO L168 Benchmark]: CDTParser took 0.55 ms. Allocated memory is still 1.0 GB. Free memory is still 987.2 MB. There was no memory consumed. Max. memory is 11.5 GB. [2019-11-27 18:47:23,280 INFO L168 Benchmark]: CACSL2BoogieTranslator took 425.55 ms. Allocated memory was 1.0 GB in the beginning and 1.2 GB in the end (delta: 148.4 MB). Free memory was 960.4 MB in the beginning and 1.1 GB in the end (delta: -178.3 MB). Peak memory consumption was 20.4 MB. Max. memory is 11.5 GB. [2019-11-27 18:47:23,281 INFO L168 Benchmark]: Boogie Procedure Inliner took 48.01 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 1.6 MB). Peak memory consumption was 1.6 MB. Max. memory is 11.5 GB. [2019-11-27 18:47:23,282 INFO L168 Benchmark]: Boogie Preprocessor took 32.75 ms. Allocated memory is still 1.2 GB. Free memory is still 1.1 GB. There was no memory consumed. Max. memory is 11.5 GB. [2019-11-27 18:47:23,283 INFO L168 Benchmark]: RCFGBuilder took 466.91 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 24.8 MB). Peak memory consumption was 24.8 MB. Max. memory is 11.5 GB. [2019-11-27 18:47:23,284 INFO L168 Benchmark]: TraceAbstraction took 1050.75 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 58.8 MB). Peak memory consumption was 58.8 MB. Max. memory is 11.5 GB. [2019-11-27 18:47:23,289 INFO L335 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.55 ms. Allocated memory is still 1.0 GB. Free memory is still 987.2 MB. There was no memory consumed. Max. memory is 11.5 GB. * CACSL2BoogieTranslator took 425.55 ms. Allocated memory was 1.0 GB in the beginning and 1.2 GB in the end (delta: 148.4 MB). Free memory was 960.4 MB in the beginning and 1.1 GB in the end (delta: -178.3 MB). Peak memory consumption was 20.4 MB. Max. memory is 11.5 GB. * Boogie Procedure Inliner took 48.01 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 1.6 MB). Peak memory consumption was 1.6 MB. Max. memory is 11.5 GB. * Boogie Preprocessor took 32.75 ms. Allocated memory is still 1.2 GB. Free memory is still 1.1 GB. There was no memory consumed. Max. memory is 11.5 GB. * RCFGBuilder took 466.91 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 24.8 MB). Peak memory consumption was 24.8 MB. Max. memory is 11.5 GB. * TraceAbstraction took 1050.75 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 58.8 MB). Peak memory consumption was 58.8 MB. Max. memory is 11.5 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: SMTLIBException: Undeclared function symbol (const Int) de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: SMTLIBException: Undeclared function symbol (const Int): de.uni_freiburg.informatik.ultimate.logic.NoopScript.term(NoopScript.java:478) RESULT: Ultimate could not prove your program: Toolchain returned no result. Received shutdown request... ### Bit-precise run ### This is Ultimate 0.1.24-3c39aff [2019-11-27 18:47:25,289 INFO L177 SettingsManager]: Resetting all preferences to default values... [2019-11-27 18:47:25,291 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2019-11-27 18:47:25,310 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2019-11-27 18:47:25,311 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2019-11-27 18:47:25,313 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2019-11-27 18:47:25,315 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2019-11-27 18:47:25,324 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2019-11-27 18:47:25,330 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2019-11-27 18:47:25,333 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2019-11-27 18:47:25,335 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2019-11-27 18:47:25,337 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2019-11-27 18:47:25,337 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2019-11-27 18:47:25,339 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2019-11-27 18:47:25,340 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2019-11-27 18:47:25,341 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2019-11-27 18:47:25,342 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2019-11-27 18:47:25,344 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2019-11-27 18:47:25,347 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2019-11-27 18:47:25,351 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2019-11-27 18:47:25,356 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2019-11-27 18:47:25,359 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2019-11-27 18:47:25,361 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2019-11-27 18:47:25,363 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2019-11-27 18:47:25,366 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2019-11-27 18:47:25,366 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2019-11-27 18:47:25,367 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2019-11-27 18:47:25,369 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2019-11-27 18:47:25,369 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2019-11-27 18:47:25,370 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2019-11-27 18:47:25,371 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2019-11-27 18:47:25,371 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2019-11-27 18:47:25,372 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2019-11-27 18:47:25,373 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2019-11-27 18:47:25,374 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2019-11-27 18:47:25,375 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2019-11-27 18:47:25,376 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2019-11-27 18:47:25,376 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2019-11-27 18:47:25,376 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2019-11-27 18:47:25,379 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2019-11-27 18:47:25,380 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2019-11-27 18:47:25,381 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf [2019-11-27 18:47:25,408 INFO L113 SettingsManager]: Loading preferences was successful [2019-11-27 18:47:25,408 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2019-11-27 18:47:25,410 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2019-11-27 18:47:25,410 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2019-11-27 18:47:25,410 INFO L138 SettingsManager]: * Use SBE=true [2019-11-27 18:47:25,411 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2019-11-27 18:47:25,411 INFO L138 SettingsManager]: * sizeof long=4 [2019-11-27 18:47:25,411 INFO L138 SettingsManager]: * sizeof POINTER=4 [2019-11-27 18:47:25,412 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2019-11-27 18:47:25,412 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2019-11-27 18:47:25,412 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2019-11-27 18:47:25,413 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2019-11-27 18:47:25,413 INFO L138 SettingsManager]: * Use bitvectors instead of ints=true [2019-11-27 18:47:25,413 INFO L138 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2019-11-27 18:47:25,413 INFO L138 SettingsManager]: * sizeof long double=12 [2019-11-27 18:47:25,414 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2019-11-27 18:47:25,414 INFO L138 SettingsManager]: * Use constant arrays=true [2019-11-27 18:47:25,414 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2019-11-27 18:47:25,415 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2019-11-27 18:47:25,415 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2019-11-27 18:47:25,415 INFO L138 SettingsManager]: * To the following directory=./dump/ [2019-11-27 18:47:25,415 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2019-11-27 18:47:25,416 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-11-27 18:47:25,416 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2019-11-27 18:47:25,416 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2019-11-27 18:47:25,417 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2019-11-27 18:47:25,417 INFO L138 SettingsManager]: * Trace refinement strategy=WOLF [2019-11-27 18:47:25,417 INFO L138 SettingsManager]: * Command for external solver=cvc4 --incremental --rewrite-divk --print-success --lang smt [2019-11-27 18:47:25,418 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2019-11-27 18:47:25,418 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2019-11-27 18:47:25,418 INFO L138 SettingsManager]: * Logic for external solver=AUFBV 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(__VERIFIER_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 -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 4f7077bba653370b680c2ff46ec9417a9e7cf514 [2019-11-27 18:47:25,753 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2019-11-27 18:47:25,767 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2019-11-27 18:47:25,770 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2019-11-27 18:47:25,771 INFO L271 PluginConnector]: Initializing CDTParser... [2019-11-27 18:47:25,772 INFO L275 PluginConnector]: CDTParser initialized [2019-11-27 18:47:25,772 INFO L428 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/verifythis/prefixsum_rec.c [2019-11-27 18:47:25,845 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/dc873447c/7da7f48c0548417fb8847698a2451f63/FLAG1c1d06536 [2019-11-27 18:47:26,283 INFO L306 CDTParser]: Found 1 translation units. [2019-11-27 18:47:26,284 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/verifythis/prefixsum_rec.c [2019-11-27 18:47:26,290 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/dc873447c/7da7f48c0548417fb8847698a2451f63/FLAG1c1d06536 [2019-11-27 18:47:26,643 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/dc873447c/7da7f48c0548417fb8847698a2451f63 [2019-11-27 18:47:26,647 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2019-11-27 18:47:26,648 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2019-11-27 18:47:26,650 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2019-11-27 18:47:26,650 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2019-11-27 18:47:26,654 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2019-11-27 18:47:26,655 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.11 06:47:26" (1/1) ... [2019-11-27 18:47:26,658 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@f4bd2a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26, skipping insertion in model container [2019-11-27 18:47:26,658 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.11 06:47:26" (1/1) ... [2019-11-27 18:47:26,666 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2019-11-27 18:47:26,688 INFO L178 MainTranslator]: Built tables and reachable declarations [2019-11-27 18:47:26,873 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-27 18:47:26,889 INFO L203 MainTranslator]: Completed pre-run [2019-11-27 18:47:26,919 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-27 18:47:26,938 INFO L208 MainTranslator]: Completed translation [2019-11-27 18:47:26,938 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26 WrapperNode [2019-11-27 18:47:26,938 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2019-11-27 18:47:26,939 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2019-11-27 18:47:26,940 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2019-11-27 18:47:26,940 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2019-11-27 18:47:27,005 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26" (1/1) ... [2019-11-27 18:47:27,031 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26" (1/1) ... [2019-11-27 18:47:27,071 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2019-11-27 18:47:27,072 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2019-11-27 18:47:27,072 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2019-11-27 18:47:27,072 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2019-11-27 18:47:27,079 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26" (1/1) ... [2019-11-27 18:47:27,080 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26" (1/1) ... [2019-11-27 18:47:27,084 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26" (1/1) ... [2019-11-27 18:47:27,085 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26" (1/1) ... [2019-11-27 18:47:27,093 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26" (1/1) ... [2019-11-27 18:47:27,099 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26" (1/1) ... [2019-11-27 18:47:27,101 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26" (1/1) ... [2019-11-27 18:47:27,104 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2019-11-27 18:47:27,105 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2019-11-27 18:47:27,105 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2019-11-27 18:47:27,106 INFO L275 PluginConnector]: RCFGBuilder initialized [2019-11-27 18:47:27,107 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-11-27 18:47:27,169 INFO L130 BoogieDeclarations]: Found specification of procedure downsweep [2019-11-27 18:47:27,170 INFO L138 BoogieDeclarations]: Found implementation of procedure downsweep [2019-11-27 18:47:27,170 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2019-11-27 18:47:27,170 INFO L130 BoogieDeclarations]: Found specification of procedure read~intINTTYPE4 [2019-11-27 18:47:27,170 INFO L130 BoogieDeclarations]: Found specification of procedure upsweep [2019-11-27 18:47:27,171 INFO L138 BoogieDeclarations]: Found implementation of procedure upsweep [2019-11-27 18:47:27,171 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2019-11-27 18:47:27,171 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2019-11-27 18:47:27,171 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2019-11-27 18:47:27,172 INFO L130 BoogieDeclarations]: Found specification of procedure write~intINTTYPE4 [2019-11-27 18:47:27,580 INFO L282 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2019-11-27 18:47:27,580 INFO L287 CfgBuilder]: Removed 17 assume(true) statements. [2019-11-27 18:47:27,582 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 06:47:27 BoogieIcfgContainer [2019-11-27 18:47:27,582 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2019-11-27 18:47:27,583 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2019-11-27 18:47:27,583 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2019-11-27 18:47:27,586 INFO L275 PluginConnector]: TraceAbstraction initialized [2019-11-27 18:47:27,586 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 27.11 06:47:26" (1/3) ... [2019-11-27 18:47:27,587 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4a0df141 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.11 06:47:27, skipping insertion in model container [2019-11-27 18:47:27,587 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.11 06:47:26" (2/3) ... [2019-11-27 18:47:27,588 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4a0df141 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.11 06:47:27, skipping insertion in model container [2019-11-27 18:47:27,588 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.11 06:47:27" (3/3) ... [2019-11-27 18:47:27,589 INFO L109 eAbstractionObserver]: Analyzing ICFG prefixsum_rec.c [2019-11-27 18:47:27,600 INFO L156 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2019-11-27 18:47:27,607 INFO L168 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2019-11-27 18:47:27,620 INFO L249 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2019-11-27 18:47:27,645 INFO L373 AbstractCegarLoop]: Interprodecural is true [2019-11-27 18:47:27,645 INFO L374 AbstractCegarLoop]: Hoare is true [2019-11-27 18:47:27,645 INFO L375 AbstractCegarLoop]: Compute interpolants for FPandBP [2019-11-27 18:47:27,646 INFO L376 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2019-11-27 18:47:27,646 INFO L377 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2019-11-27 18:47:27,646 INFO L378 AbstractCegarLoop]: Difference is false [2019-11-27 18:47:27,646 INFO L379 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2019-11-27 18:47:27,646 INFO L383 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2019-11-27 18:47:27,662 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states. [2019-11-27 18:47:27,668 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2019-11-27 18:47:27,669 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:47:27,670 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-27 18:47:27,670 INFO L410 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:47:27,674 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:47:27,675 INFO L82 PathProgramCache]: Analyzing trace with hash -1360829009, now seen corresponding path program 1 times [2019-11-27 18:47:27,686 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-27 18:47:27,686 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1477675734] [2019-11-27 18:47:27,687 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 2 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with mathsat -unsat_core_generation=3 [2019-11-27 18:47:27,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-27 18:47:27,832 INFO L255 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 5 conjunts are in the unsatisfiable core [2019-11-27 18:47:27,840 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-27 18:47:27,882 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:47:27,934 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-27 18:47:27,935 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-27 18:47:27,977 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-27 18:47:27,978 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1477675734] [2019-11-27 18:47:27,980 INFO L220 FreeRefinementEngine]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2019-11-27 18:47:27,980 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4, 4] imperfect sequences [] total 5 [2019-11-27 18:47:27,981 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1362092258] [2019-11-27 18:47:27,987 INFO L442 AbstractCegarLoop]: Interpolant automaton has 5 states [2019-11-27 18:47:27,987 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-27 18:47:28,002 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2019-11-27 18:47:28,003 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2019-11-27 18:47:28,005 INFO L87 Difference]: Start difference. First operand 36 states. Second operand 5 states. [2019-11-27 18:47:28,109 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-27 18:47:28,109 INFO L93 Difference]: Finished difference Result 72 states and 96 transitions. [2019-11-27 18:47:28,110 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2019-11-27 18:47:28,112 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 24 [2019-11-27 18:47:28,112 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-27 18:47:28,121 INFO L225 Difference]: With dead ends: 72 [2019-11-27 18:47:28,121 INFO L226 Difference]: Without dead ends: 33 [2019-11-27 18:47:28,125 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2019-11-27 18:47:28,139 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2019-11-27 18:47:28,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2019-11-27 18:47:28,162 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2019-11-27 18:47:28,164 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 41 transitions. [2019-11-27 18:47:28,166 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 41 transitions. Word has length 24 [2019-11-27 18:47:28,166 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-27 18:47:28,167 INFO L462 AbstractCegarLoop]: Abstraction has 33 states and 41 transitions. [2019-11-27 18:47:28,167 INFO L463 AbstractCegarLoop]: Interpolant automaton has 5 states. [2019-11-27 18:47:28,167 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 41 transitions. [2019-11-27 18:47:28,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2019-11-27 18:47:28,170 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:47:28,170 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-27 18:47:28,380 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 mathsat -unsat_core_generation=3 [2019-11-27 18:47:28,386 INFO L410 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:47:28,386 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:47:28,387 INFO L82 PathProgramCache]: Analyzing trace with hash 1851866079, now seen corresponding path program 1 times [2019-11-27 18:47:28,388 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-27 18:47:28,388 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [2030055708] [2019-11-27 18:47:28,391 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 3 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with mathsat -unsat_core_generation=3 [2019-11-27 18:47:28,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-27 18:47:28,475 INFO L255 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 8 conjunts are in the unsatisfiable core [2019-11-27 18:47:28,478 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-27 18:47:28,556 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:47:28,604 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-27 18:47:28,604 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-27 18:47:28,753 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-27 18:47:28,754 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [2030055708] [2019-11-27 18:47:28,754 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-27 18:47:28,754 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2019-11-27 18:47:28,756 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1040992460] [2019-11-27 18:47:28,759 INFO L442 AbstractCegarLoop]: Interpolant automaton has 12 states [2019-11-27 18:47:28,759 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-27 18:47:28,760 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2019-11-27 18:47:28,761 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2019-11-27 18:47:28,762 INFO L87 Difference]: Start difference. First operand 33 states and 41 transitions. Second operand 12 states. [2019-11-27 18:47:29,257 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-27 18:47:29,259 INFO L93 Difference]: Finished difference Result 77 states and 98 transitions. [2019-11-27 18:47:29,260 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2019-11-27 18:47:29,260 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 25 [2019-11-27 18:47:29,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-27 18:47:29,262 INFO L225 Difference]: With dead ends: 77 [2019-11-27 18:47:29,264 INFO L226 Difference]: Without dead ends: 54 [2019-11-27 18:47:29,268 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=100, Invalid=172, Unknown=0, NotChecked=0, Total=272 [2019-11-27 18:47:29,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2019-11-27 18:47:29,293 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 41. [2019-11-27 18:47:29,293 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2019-11-27 18:47:29,297 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 50 transitions. [2019-11-27 18:47:29,298 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 50 transitions. Word has length 25 [2019-11-27 18:47:29,299 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-27 18:47:29,300 INFO L462 AbstractCegarLoop]: Abstraction has 41 states and 50 transitions. [2019-11-27 18:47:29,302 INFO L463 AbstractCegarLoop]: Interpolant automaton has 12 states. [2019-11-27 18:47:29,303 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 50 transitions. [2019-11-27 18:47:29,305 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2019-11-27 18:47:29,306 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:47:29,307 INFO L410 BasicCegarLoop]: trace histogram [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] [2019-11-27 18:47:29,527 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 mathsat -unsat_core_generation=3 [2019-11-27 18:47:29,528 INFO L410 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:47:29,528 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:47:29,529 INFO L82 PathProgramCache]: Analyzing trace with hash 1995858989, now seen corresponding path program 1 times [2019-11-27 18:47:29,530 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-27 18:47:29,530 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1708839593] [2019-11-27 18:47:29,530 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 4 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with mathsat -unsat_core_generation=3 [2019-11-27 18:47:29,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-27 18:47:29,620 INFO L255 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 10 conjunts are in the unsatisfiable core [2019-11-27 18:47:29,623 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-27 18:47:29,709 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:47:29,809 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-27 18:47:29,810 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-27 18:47:30,048 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-27 18:47:30,048 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1708839593] [2019-11-27 18:47:30,049 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-27 18:47:30,050 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2019-11-27 18:47:30,050 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1632552835] [2019-11-27 18:47:30,051 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2019-11-27 18:47:30,051 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-27 18:47:30,051 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2019-11-27 18:47:30,052 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=166, Unknown=0, NotChecked=0, Total=240 [2019-11-27 18:47:30,052 INFO L87 Difference]: Start difference. First operand 41 states and 50 transitions. Second operand 16 states. [2019-11-27 18:47:31,052 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-27 18:47:31,052 INFO L93 Difference]: Finished difference Result 103 states and 129 transitions. [2019-11-27 18:47:31,054 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2019-11-27 18:47:31,054 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 28 [2019-11-27 18:47:31,054 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-27 18:47:31,055 INFO L225 Difference]: With dead ends: 103 [2019-11-27 18:47:31,055 INFO L226 Difference]: Without dead ends: 80 [2019-11-27 18:47:31,057 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=208, Invalid=442, Unknown=0, NotChecked=0, Total=650 [2019-11-27 18:47:31,057 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2019-11-27 18:47:31,066 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 46. [2019-11-27 18:47:31,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2019-11-27 18:47:31,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 56 transitions. [2019-11-27 18:47:31,068 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 56 transitions. Word has length 28 [2019-11-27 18:47:31,068 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-27 18:47:31,068 INFO L462 AbstractCegarLoop]: Abstraction has 46 states and 56 transitions. [2019-11-27 18:47:31,068 INFO L463 AbstractCegarLoop]: Interpolant automaton has 16 states. [2019-11-27 18:47:31,068 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 56 transitions. [2019-11-27 18:47:31,070 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2019-11-27 18:47:31,070 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:47:31,070 INFO L410 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-27 18:47:31,281 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 mathsat -unsat_core_generation=3 [2019-11-27 18:47:31,281 INFO L410 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:47:31,282 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:47:31,282 INFO L82 PathProgramCache]: Analyzing trace with hash -1266553509, now seen corresponding path program 2 times [2019-11-27 18:47:31,283 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-27 18:47:31,284 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [321936565] [2019-11-27 18:47:31,284 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 5 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with mathsat -unsat_core_generation=3 [2019-11-27 18:47:31,390 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2019-11-27 18:47:31,391 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-27 18:47:31,402 INFO L255 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 33 conjunts are in the unsatisfiable core [2019-11-27 18:47:31,405 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-27 18:47:31,930 WARN L192 SmtUtils]: Spent 234.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 13 [2019-11-27 18:47:32,010 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2019-11-27 18:47:32,011 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:47:32,169 WARN L192 SmtUtils]: Spent 157.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2019-11-27 18:47:32,170 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:47:32,171 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:47:32,171 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:31, output treesize:27 [2019-11-27 18:47:32,595 WARN L192 SmtUtils]: Spent 170.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2019-11-27 18:47:32,890 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:47:32,897 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:47:32,897 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 70 treesize of output 32 [2019-11-27 18:47:32,898 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:47:33,052 WARN L192 SmtUtils]: Spent 152.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2019-11-27 18:47:33,052 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:47:33,053 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-27 18:47:33,054 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:84, output treesize:29 [2019-11-27 18:47:33,884 WARN L192 SmtUtils]: Spent 175.00 ms on a formula simplification that was a NOOP. DAG size: 28 [2019-11-27 18:47:33,888 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:47:34,104 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2019-11-27 18:47:34,104 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-27 18:47:35,199 WARN L192 SmtUtils]: Spent 455.00 ms on a formula simplification that was a NOOP. DAG size: 46 [2019-11-27 18:47:35,567 WARN L192 SmtUtils]: Spent 367.00 ms on a formula simplification that was a NOOP. DAG size: 44 [2019-11-27 18:47:39,159 WARN L192 SmtUtils]: Spent 139.00 ms on a formula simplification that was a NOOP. DAG size: 33 [2019-11-27 18:47:42,255 WARN L192 SmtUtils]: Spent 119.00 ms on a formula simplification that was a NOOP. DAG size: 40 [2019-11-27 18:47:42,264 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 44 treesize of output 40 [2019-11-27 18:47:42,357 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:47:42,357 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 116 treesize of output 120 [2019-11-27 18:47:42,358 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:47:42,358 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:47:42,360 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:47:42,360 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:47:42,361 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:47:42,362 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:47:42,363 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:47:42,365 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2019-11-27 18:47:42,674 WARN L192 SmtUtils]: Spent 308.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 9 [2019-11-27 18:47:42,675 INFO L588 ElimStorePlain]: treesize reduction 281, result has 3.4 percent of original size [2019-11-27 18:47:42,675 INFO L508 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:47:42,715 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:47:42,715 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:47:42,715 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:44, output treesize:10 [2019-11-27 18:47:43,749 WARN L192 SmtUtils]: Spent 227.00 ms on a formula simplification that was a NOOP. DAG size: 24 [2019-11-27 18:47:44,031 WARN L192 SmtUtils]: Spent 281.00 ms on a formula simplification that was a NOOP. DAG size: 24 [2019-11-27 18:47:46,286 WARN L192 SmtUtils]: Spent 279.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 18 [2019-11-27 18:47:47,381 WARN L192 SmtUtils]: Spent 130.00 ms on a formula simplification that was a NOOP. DAG size: 23 [2019-11-27 18:47:47,471 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2019-11-27 18:47:47,472 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [321936565] [2019-11-27 18:47:47,472 INFO L220 FreeRefinementEngine]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2019-11-27 18:47:47,472 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14, 12] imperfect sequences [] total 24 [2019-11-27 18:47:47,472 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1050030954] [2019-11-27 18:47:47,473 INFO L442 AbstractCegarLoop]: Interpolant automaton has 24 states [2019-11-27 18:47:47,473 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-27 18:47:47,473 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2019-11-27 18:47:47,474 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=482, Unknown=2, NotChecked=0, Total=552 [2019-11-27 18:47:47,474 INFO L87 Difference]: Start difference. First operand 46 states and 56 transitions. Second operand 24 states. [2019-11-27 18:48:05,106 WARN L192 SmtUtils]: Spent 283.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 15 [2019-11-27 18:48:06,185 WARN L192 SmtUtils]: Spent 342.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 24 [2019-11-27 18:48:19,258 WARN L192 SmtUtils]: Spent 8.27 s on a formula simplification that was a NOOP. DAG size: 42 [2019-11-27 18:48:28,689 WARN L192 SmtUtils]: Spent 8.28 s on a formula simplification that was a NOOP. DAG size: 42 [2019-11-27 18:48:33,153 WARN L192 SmtUtils]: Spent 660.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 26 [2019-11-27 18:48:38,258 WARN L192 SmtUtils]: Spent 1.52 s on a formula simplification. DAG size of input: 41 DAG size of output: 39 [2019-11-27 18:48:45,405 WARN L192 SmtUtils]: Spent 1.70 s on a formula simplification. DAG size of input: 44 DAG size of output: 42 [2019-11-27 18:48:50,456 WARN L192 SmtUtils]: Spent 743.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 29 [2019-11-27 18:48:54,680 WARN L192 SmtUtils]: Spent 782.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 29 [2019-11-27 18:48:57,120 WARN L192 SmtUtils]: Spent 327.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 18 [2019-11-27 18:49:01,099 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-27 18:49:01,099 INFO L93 Difference]: Finished difference Result 81 states and 99 transitions. [2019-11-27 18:49:01,106 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2019-11-27 18:49:01,106 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 29 [2019-11-27 18:49:01,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-27 18:49:01,109 INFO L225 Difference]: With dead ends: 81 [2019-11-27 18:49:01,109 INFO L226 Difference]: Without dead ends: 79 [2019-11-27 18:49:01,111 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 33 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 53.7s TimeCoverageRelationStatistics Valid=226, Invalid=1250, Unknown=6, NotChecked=0, Total=1482 [2019-11-27 18:49:01,111 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2019-11-27 18:49:01,125 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 60. [2019-11-27 18:49:01,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2019-11-27 18:49:01,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 76 transitions. [2019-11-27 18:49:01,128 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 76 transitions. Word has length 29 [2019-11-27 18:49:01,128 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-27 18:49:01,128 INFO L462 AbstractCegarLoop]: Abstraction has 60 states and 76 transitions. [2019-11-27 18:49:01,129 INFO L463 AbstractCegarLoop]: Interpolant automaton has 24 states. [2019-11-27 18:49:01,129 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 76 transitions. [2019-11-27 18:49:01,130 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2019-11-27 18:49:01,131 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:49:01,131 INFO L410 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-27 18:49:01,333 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 mathsat -unsat_core_generation=3 [2019-11-27 18:49:01,334 INFO L410 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:49:01,335 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:49:01,336 INFO L82 PathProgramCache]: Analyzing trace with hash -1543543150, now seen corresponding path program 1 times [2019-11-27 18:49:01,337 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-27 18:49:01,337 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [586720212] [2019-11-27 18:49:01,337 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 6 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with mathsat -unsat_core_generation=3 [2019-11-27 18:49:01,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-27 18:49:01,537 WARN L253 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 62 conjunts are in the unsatisfiable core [2019-11-27 18:49:01,540 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-27 18:49:01,597 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:49:01,604 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2019-11-27 18:49:01,604 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:49:01,638 INFO L588 ElimStorePlain]: treesize reduction 6, result has 81.3 percent of original size [2019-11-27 18:49:01,643 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 6 [2019-11-27 18:49:01,644 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-27 18:49:01,667 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:49:01,668 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:49:01,668 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:33, output treesize:25 [2019-11-27 18:49:01,726 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:49:01,726 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 13 treesize of output 17 [2019-11-27 18:49:01,727 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:49:01,747 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:49:01,754 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2019-11-27 18:49:01,755 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-27 18:49:01,771 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:49:01,772 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:49:01,772 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:42, output treesize:33 [2019-11-27 18:49:01,856 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 32 [2019-11-27 18:49:01,857 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:49:01,887 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:49:01,887 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:49:01,888 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:59, output treesize:51 [2019-11-27 18:49:02,026 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 28 [2019-11-27 18:49:02,027 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:49:02,056 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:49:02,056 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:49:02,057 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:52, output treesize:43 [2019-11-27 18:49:02,328 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 61 treesize of output 55 [2019-11-27 18:49:02,329 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:49:02,349 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:49:02,349 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:49:02,350 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:81, output treesize:71 [2019-11-27 18:49:02,384 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 39 treesize of output 37 [2019-11-27 18:49:02,385 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:49:02,405 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:49:02,406 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:49:02,406 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:59, output treesize:51 [2019-11-27 18:49:04,475 WARN L860 $PredicateComparison]: unable to prove that (exists ((downsweep_~tmp~0 (_ BitVec 32))) (= |c_#memory_int| (store |c_old(#memory_int)| |c_downsweep_#in~a.base| (let ((.cse2 (bvadd (bvmul |c_downsweep_#in~left| (_ bv4 32)) |c_downsweep_#in~a.offset|))) (store (let ((.cse0 (select |c_old(#memory_int)| |c_downsweep_#in~a.base|)) (.cse1 (bvadd |c_downsweep_#in~a.offset| (bvmul |c_downsweep_#in~right| (_ bv4 32))))) (store .cse0 .cse1 (bvadd (select .cse0 .cse2) (select .cse0 .cse1)))) .cse2 downsweep_~tmp~0))))) is different from true [2019-11-27 18:49:04,497 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 71 treesize of output 65 [2019-11-27 18:49:04,498 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:49:04,697 WARN L192 SmtUtils]: Spent 199.00 ms on a formula simplification that was a NOOP. DAG size: 40 [2019-11-27 18:49:04,698 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:49:04,699 INFO L508 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2019-11-27 18:49:04,699 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:91, output treesize:81 [2019-11-27 18:49:07,113 WARN L192 SmtUtils]: Spent 2.10 s on a formula simplification that was a NOOP. DAG size: 42 [2019-11-27 18:49:09,564 WARN L192 SmtUtils]: Spent 2.14 s on a formula simplification that was a NOOP. DAG size: 44 [2019-11-27 18:49:12,042 WARN L192 SmtUtils]: Spent 2.12 s on a formula simplification that was a NOOP. DAG size: 46 [2019-11-27 18:49:14,504 WARN L192 SmtUtils]: Spent 2.11 s on a formula simplification that was a NOOP. DAG size: 49 [2019-11-27 18:49:14,508 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:49:14,647 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-27 18:49:14,648 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-27 18:49:15,944 WARN L192 SmtUtils]: Spent 456.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2019-11-27 18:49:16,450 WARN L192 SmtUtils]: Spent 505.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2019-11-27 18:49:19,234 WARN L192 SmtUtils]: Spent 178.00 ms on a formula simplification that was a NOOP. DAG size: 44 [2019-11-27 18:49:25,129 WARN L192 SmtUtils]: Spent 222.00 ms on a formula simplification that was a NOOP. DAG size: 53 [2019-11-27 18:49:26,909 WARN L192 SmtUtils]: Spent 277.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2019-11-27 18:49:27,145 WARN L192 SmtUtils]: Spent 235.00 ms on a formula simplification that was a NOOP. DAG size: 41 [2019-11-27 18:49:28,999 WARN L192 SmtUtils]: Spent 161.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2019-11-27 18:49:31,337 WARN L192 SmtUtils]: Spent 220.00 ms on a formula simplification that was a NOOP. DAG size: 64 [2019-11-27 18:49:40,041 WARN L192 SmtUtils]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2019-11-27 18:49:49,874 INFO L377 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 10 treesize of output 8 [2019-11-27 18:49:49,874 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:49:50,011 WARN L192 SmtUtils]: Spent 136.00 ms on a formula simplification that was a NOOP. DAG size: 39 [2019-11-27 18:49:50,011 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:49:50,018 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-27 18:49:50,020 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-27 18:49:50,124 WARN L192 SmtUtils]: Spent 103.00 ms on a formula simplification that was a NOOP. DAG size: 29 [2019-11-27 18:49:50,125 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:49:50,125 INFO L508 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-27 18:49:50,125 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:360, output treesize:57 [2019-11-27 18:49:54,518 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-27 18:49:54,519 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [586720212] [2019-11-27 18:49:54,519 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-27 18:49:54,519 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 21] total 38 [2019-11-27 18:49:54,519 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1619679338] [2019-11-27 18:49:54,520 INFO L442 AbstractCegarLoop]: Interpolant automaton has 38 states [2019-11-27 18:49:54,520 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-27 18:49:54,520 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2019-11-27 18:49:54,521 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=1199, Unknown=7, NotChecked=70, Total=1406 [2019-11-27 18:49:54,522 INFO L87 Difference]: Start difference. First operand 60 states and 76 transitions. Second operand 38 states. [2019-11-27 18:49:56,895 WARN L192 SmtUtils]: Spent 294.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 34 [2019-11-27 18:49:58,729 WARN L192 SmtUtils]: Spent 281.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 42 [2019-11-27 18:50:01,252 WARN L192 SmtUtils]: Spent 217.00 ms on a formula simplification that was a NOOP. DAG size: 39 [2019-11-27 18:50:03,305 WARN L192 SmtUtils]: Spent 293.00 ms on a formula simplification that was a NOOP. DAG size: 42 [2019-11-27 18:50:04,100 WARN L192 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 47 [2019-11-27 18:50:11,950 WARN L192 SmtUtils]: Spent 394.00 ms on a formula simplification that was a NOOP. DAG size: 75 [2019-11-27 18:50:19,414 WARN L192 SmtUtils]: Spent 680.00 ms on a formula simplification that was a NOOP. DAG size: 71 [2019-11-27 18:50:20,217 WARN L192 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 47 [2019-11-27 18:50:29,806 WARN L192 SmtUtils]: Spent 2.99 s on a formula simplification that was a NOOP. DAG size: 98 [2019-11-27 18:50:39,894 WARN L192 SmtUtils]: Spent 1.83 s on a formula simplification that was a NOOP. DAG size: 90 [2019-11-27 18:50:40,616 WARN L192 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 50 [2019-11-27 18:50:45,347 WARN L192 SmtUtils]: Spent 648.00 ms on a formula simplification that was a NOOP. DAG size: 70 [2019-11-27 18:50:53,184 WARN L192 SmtUtils]: Spent 1.08 s on a formula simplification that was a NOOP. DAG size: 80 [2019-11-27 18:51:04,059 WARN L192 SmtUtils]: Spent 614.00 ms on a formula simplification that was a NOOP. DAG size: 61 [2019-11-27 18:51:38,203 WARN L192 SmtUtils]: Spent 6.45 s on a formula simplification that was a NOOP. DAG size: 62 [2019-11-27 18:51:41,588 WARN L860 $PredicateComparison]: unable to prove that (and (or (not (= (bvadd |c_downsweep_#in~left| (_ bv1 32)) (bvsdiv (bvadd |c_downsweep_#in~right| (_ bv1 32)) (_ bv2 32)))) (forall ((v_ULTIMATE.start_main_~a0~0.offset_BEFORE_CALL_3 (_ BitVec 32)) (v_ULTIMATE.start_main_~a0~0.base_BEFORE_CALL_3 (_ BitVec 32))) (or (= (select (select |c_#memory_int| v_ULTIMATE.start_main_~a0~0.base_BEFORE_CALL_3) v_ULTIMATE.start_main_~a0~0.offset_BEFORE_CALL_3) (select (select |c_#memory_int| |c_downsweep_#in~a.base|) (bvadd |c_downsweep_#in~a.offset| (_ bv4 32)))) (exists ((v_downsweep_~tmp~0_17 (_ BitVec 32))) (not (let ((.cse0 (let ((.cse3 (bvadd (bvmul (bvsdiv (bvadd |c_downsweep_#in~right| (_ bv1 32)) (_ bv2 32)) (_ bv4 32)) |c_downsweep_#in~a.offset| (_ bv4294967292 32)))) (store (let ((.cse1 (select |c_old(#memory_int)| |c_downsweep_#in~a.base|)) (.cse2 (bvadd |c_downsweep_#in~a.offset| (bvmul |c_downsweep_#in~right| (_ bv4 32))))) (store .cse1 .cse2 (bvadd (select .cse1 .cse3) (select .cse1 .cse2)))) .cse3 v_downsweep_~tmp~0_17)))) (= (select .cse0 (bvadd |c_downsweep_#in~a.offset| (_ bv4 32))) (select (select (store |c_old(#memory_int)| |c_downsweep_#in~a.base| .cse0) v_ULTIMATE.start_main_~a0~0.base_BEFORE_CALL_3) v_ULTIMATE.start_main_~a0~0.offset_BEFORE_CALL_3)))))))) (exists ((downsweep_~tmp~0 (_ BitVec 32))) (= |c_#memory_int| (store |c_old(#memory_int)| |c_downsweep_#in~a.base| (let ((.cse6 (bvadd (bvmul |c_downsweep_#in~left| (_ bv4 32)) |c_downsweep_#in~a.offset|))) (store (let ((.cse4 (select |c_old(#memory_int)| |c_downsweep_#in~a.base|)) (.cse5 (bvadd |c_downsweep_#in~a.offset| (bvmul |c_downsweep_#in~right| (_ bv4 32))))) (store .cse4 .cse5 (bvadd (select .cse4 .cse6) (select .cse4 .cse5)))) .cse6 downsweep_~tmp~0)))))) is different from true [2019-11-27 18:51:52,471 WARN L192 SmtUtils]: Spent 4.39 s on a formula simplification that was a NOOP. DAG size: 69 [2019-11-27 18:51:59,279 WARN L192 SmtUtils]: Spent 4.54 s on a formula simplification that was a NOOP. DAG size: 72 [2019-11-27 18:52:08,774 WARN L192 SmtUtils]: Spent 4.39 s on a formula simplification that was a NOOP. DAG size: 86 [2019-11-27 18:52:17,540 WARN L192 SmtUtils]: Spent 6.37 s on a formula simplification that was a NOOP. DAG size: 86 [2019-11-27 18:52:26,951 WARN L192 SmtUtils]: Spent 4.32 s on a formula simplification that was a NOOP. DAG size: 77 [2019-11-27 18:52:31,033 WARN L192 SmtUtils]: Spent 2.18 s on a formula simplification that was a NOOP. DAG size: 58 [2019-11-27 18:52:35,036 WARN L192 SmtUtils]: Spent 2.13 s on a formula simplification that was a NOOP. DAG size: 46 [2019-11-27 18:52:38,427 WARN L192 SmtUtils]: Spent 2.13 s on a formula simplification that was a NOOP. DAG size: 45 [2019-11-27 18:52:48,045 WARN L192 SmtUtils]: Spent 888.00 ms on a formula simplification that was a NOOP. DAG size: 72 [2019-11-27 18:53:00,070 WARN L192 SmtUtils]: Spent 6.26 s on a formula simplification that was a NOOP. DAG size: 55 [2019-11-27 18:53:10,782 WARN L192 SmtUtils]: Spent 7.83 s on a formula simplification. DAG size of input: 112 DAG size of output: 103 [2019-11-27 18:53:16,018 WARN L192 SmtUtils]: Spent 327.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2019-11-27 18:53:26,272 WARN L192 SmtUtils]: Spent 7.93 s on a formula simplification. DAG size of input: 115 DAG size of output: 106 [2019-11-27 18:53:41,084 WARN L192 SmtUtils]: Spent 127.00 ms on a formula simplification that was a NOOP. DAG size: 38 [2019-11-27 18:53:42,749 WARN L192 SmtUtils]: Spent 458.00 ms on a formula simplification that was a NOOP. DAG size: 53 [2019-11-27 18:53:44,772 WARN L192 SmtUtils]: Spent 398.00 ms on a formula simplification that was a NOOP. DAG size: 70 [2019-11-27 18:53:47,008 WARN L192 SmtUtils]: Spent 404.00 ms on a formula simplification that was a NOOP. DAG size: 73 [2019-11-27 18:53:48,936 WARN L192 SmtUtils]: Spent 366.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2019-11-27 18:53:50,677 WARN L192 SmtUtils]: Spent 365.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2019-11-27 18:53:52,520 WARN L192 SmtUtils]: Spent 356.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2019-11-27 18:53:55,436 WARN L192 SmtUtils]: Spent 533.00 ms on a formula simplification that was a NOOP. DAG size: 56 [2019-11-27 18:53:57,648 WARN L192 SmtUtils]: Spent 404.00 ms on a formula simplification that was a NOOP. DAG size: 56 [2019-11-27 18:54:05,819 WARN L192 SmtUtils]: Spent 309.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 45 [2019-11-27 18:54:06,023 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-27 18:54:06,023 INFO L93 Difference]: Finished difference Result 178 states and 219 transitions. [2019-11-27 18:54:06,030 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2019-11-27 18:54:06,030 INFO L78 Accepts]: Start accepts. Automaton has 38 states. Word has length 33 [2019-11-27 18:54:06,031 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-27 18:54:06,033 INFO L225 Difference]: With dead ends: 178 [2019-11-27 18:54:06,033 INFO L226 Difference]: Without dead ends: 176 [2019-11-27 18:54:06,035 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 28 SyntacticMatches, 3 SemanticMatches, 79 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 1024 ImplicationChecksByTransitivity, 201.6s TimeCoverageRelationStatistics Valid=674, Invalid=5480, Unknown=16, NotChecked=310, Total=6480 [2019-11-27 18:54:06,036 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 176 states. [2019-11-27 18:54:06,061 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 176 to 99. [2019-11-27 18:54:06,061 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 99 states. [2019-11-27 18:54:06,063 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 126 transitions. [2019-11-27 18:54:06,063 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 126 transitions. Word has length 33 [2019-11-27 18:54:06,064 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-27 18:54:06,064 INFO L462 AbstractCegarLoop]: Abstraction has 99 states and 126 transitions. [2019-11-27 18:54:06,064 INFO L463 AbstractCegarLoop]: Interpolant automaton has 38 states. [2019-11-27 18:54:06,064 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 126 transitions. [2019-11-27 18:54:06,066 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2019-11-27 18:54:06,067 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:54:06,067 INFO L410 BasicCegarLoop]: trace histogram [4, 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] [2019-11-27 18:54:06,270 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 mathsat -unsat_core_generation=3 [2019-11-27 18:54:06,271 INFO L410 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:54:06,271 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:54:06,272 INFO L82 PathProgramCache]: Analyzing trace with hash 619891810, now seen corresponding path program 2 times [2019-11-27 18:54:06,272 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-27 18:54:06,273 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1555681329] [2019-11-27 18:54:06,273 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 7 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with mathsat -unsat_core_generation=3 [2019-11-27 18:54:06,364 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-27 18:54:06,365 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-27 18:54:06,373 INFO L255 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 11 conjunts are in the unsatisfiable core [2019-11-27 18:54:06,377 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-27 18:54:06,486 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2019-11-27 18:54:06,486 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-27 18:54:06,910 WARN L192 SmtUtils]: Spent 397.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2019-11-27 18:54:07,092 WARN L192 SmtUtils]: Spent 182.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2019-11-27 18:54:08,125 WARN L192 SmtUtils]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2019-11-27 18:54:09,289 WARN L192 SmtUtils]: Spent 156.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2019-11-27 18:54:10,107 WARN L192 SmtUtils]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2019-11-27 18:54:10,626 WARN L192 SmtUtils]: Spent 127.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2019-11-27 18:54:10,662 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2019-11-27 18:54:10,662 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1555681329] [2019-11-27 18:54:10,662 INFO L220 FreeRefinementEngine]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2019-11-27 18:54:10,662 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 12 [2019-11-27 18:54:10,663 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1280302069] [2019-11-27 18:54:10,663 INFO L442 AbstractCegarLoop]: Interpolant automaton has 7 states [2019-11-27 18:54:10,663 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-27 18:54:10,663 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2019-11-27 18:54:10,664 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2019-11-27 18:54:10,664 INFO L87 Difference]: Start difference. First operand 99 states and 126 transitions. Second operand 7 states. [2019-11-27 18:54:13,158 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-27 18:54:13,158 INFO L93 Difference]: Finished difference Result 137 states and 169 transitions. [2019-11-27 18:54:13,172 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2019-11-27 18:54:13,172 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 36 [2019-11-27 18:54:13,172 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-27 18:54:13,173 INFO L225 Difference]: With dead ends: 137 [2019-11-27 18:54:13,174 INFO L226 Difference]: Without dead ends: 102 [2019-11-27 18:54:13,175 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 59 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2019-11-27 18:54:13,175 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2019-11-27 18:54:13,201 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 82. [2019-11-27 18:54:13,202 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 82 states. [2019-11-27 18:54:13,203 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 100 transitions. [2019-11-27 18:54:13,203 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 100 transitions. Word has length 36 [2019-11-27 18:54:13,203 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-27 18:54:13,204 INFO L462 AbstractCegarLoop]: Abstraction has 82 states and 100 transitions. [2019-11-27 18:54:13,204 INFO L463 AbstractCegarLoop]: Interpolant automaton has 7 states. [2019-11-27 18:54:13,204 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 100 transitions. [2019-11-27 18:54:13,206 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2019-11-27 18:54:13,206 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:54:13,206 INFO L410 BasicCegarLoop]: trace histogram [3, 3, 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] [2019-11-27 18:54:13,426 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 mathsat -unsat_core_generation=3 [2019-11-27 18:54:13,426 INFO L410 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:54:13,426 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:54:13,426 INFO L82 PathProgramCache]: Analyzing trace with hash 1468501563, now seen corresponding path program 1 times [2019-11-27 18:54:13,426 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-27 18:54:13,427 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [722182964] [2019-11-27 18:54:13,427 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 8 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with mathsat -unsat_core_generation=3 [2019-11-27 18:54:13,509 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-27 18:54:13,518 INFO L255 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 12 conjunts are in the unsatisfiable core [2019-11-27 18:54:13,520 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-27 18:54:13,574 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:54:13,665 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2019-11-27 18:54:13,666 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-27 18:54:13,879 WARN L192 SmtUtils]: Spent 166.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-27 18:54:14,041 WARN L192 SmtUtils]: Spent 162.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-27 18:54:15,345 WARN L192 SmtUtils]: Spent 115.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2019-11-27 18:54:16,647 WARN L192 SmtUtils]: Spent 147.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2019-11-27 18:54:17,681 WARN L192 SmtUtils]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2019-11-27 18:54:18,204 WARN L192 SmtUtils]: Spent 107.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2019-11-27 18:54:18,811 WARN L192 SmtUtils]: Spent 163.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2019-11-27 18:54:18,835 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2019-11-27 18:54:18,836 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [722182964] [2019-11-27 18:54:18,836 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-27 18:54:18,836 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2019-11-27 18:54:18,836 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2079132495] [2019-11-27 18:54:18,836 INFO L442 AbstractCegarLoop]: Interpolant automaton has 14 states [2019-11-27 18:54:18,836 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-27 18:54:18,837 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2019-11-27 18:54:18,837 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2019-11-27 18:54:18,837 INFO L87 Difference]: Start difference. First operand 82 states and 100 transitions. Second operand 14 states. [2019-11-27 18:54:19,414 WARN L192 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 22 [2019-11-27 18:54:20,028 WARN L192 SmtUtils]: Spent 172.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 30 [2019-11-27 18:54:23,084 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-27 18:54:23,084 INFO L93 Difference]: Finished difference Result 98 states and 118 transitions. [2019-11-27 18:54:23,092 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2019-11-27 18:54:23,092 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 39 [2019-11-27 18:54:23,093 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-27 18:54:23,094 INFO L225 Difference]: With dead ends: 98 [2019-11-27 18:54:23,094 INFO L226 Difference]: Without dead ends: 91 [2019-11-27 18:54:23,094 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 64 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=70, Invalid=236, Unknown=0, NotChecked=0, Total=306 [2019-11-27 18:54:23,095 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2019-11-27 18:54:23,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 84. [2019-11-27 18:54:23,110 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 84 states. [2019-11-27 18:54:23,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 102 transitions. [2019-11-27 18:54:23,111 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 102 transitions. Word has length 39 [2019-11-27 18:54:23,112 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-27 18:54:23,112 INFO L462 AbstractCegarLoop]: Abstraction has 84 states and 102 transitions. [2019-11-27 18:54:23,112 INFO L463 AbstractCegarLoop]: Interpolant automaton has 14 states. [2019-11-27 18:54:23,112 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 102 transitions. [2019-11-27 18:54:23,114 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2019-11-27 18:54:23,114 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:54:23,114 INFO L410 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 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] [2019-11-27 18:54:23,335 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 mathsat -unsat_core_generation=3 [2019-11-27 18:54:23,335 INFO L410 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:54:23,335 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:54:23,335 INFO L82 PathProgramCache]: Analyzing trace with hash -1690437395, now seen corresponding path program 1 times [2019-11-27 18:54:23,336 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-27 18:54:23,337 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [766940738] [2019-11-27 18:54:23,337 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 9 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with mathsat -unsat_core_generation=3 [2019-11-27 18:54:23,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-27 18:54:23,422 INFO L255 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 12 conjunts are in the unsatisfiable core [2019-11-27 18:54:23,424 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-27 18:54:23,522 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:54:23,608 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2019-11-27 18:54:23,608 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-27 18:54:23,919 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2019-11-27 18:54:23,920 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [766940738] [2019-11-27 18:54:23,920 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-27 18:54:23,920 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2019-11-27 18:54:23,920 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1711552095] [2019-11-27 18:54:23,921 INFO L442 AbstractCegarLoop]: Interpolant automaton has 20 states [2019-11-27 18:54:23,921 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-27 18:54:23,921 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2019-11-27 18:54:23,921 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=287, Unknown=0, NotChecked=0, Total=380 [2019-11-27 18:54:23,921 INFO L87 Difference]: Start difference. First operand 84 states and 102 transitions. Second operand 20 states. [2019-11-27 18:54:26,025 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-27 18:54:26,026 INFO L93 Difference]: Finished difference Result 168 states and 209 transitions. [2019-11-27 18:54:26,027 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2019-11-27 18:54:26,027 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 43 [2019-11-27 18:54:26,028 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-27 18:54:26,032 INFO L225 Difference]: With dead ends: 168 [2019-11-27 18:54:26,034 INFO L226 Difference]: Without dead ends: 136 [2019-11-27 18:54:26,036 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 66 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 212 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=367, Invalid=1039, Unknown=0, NotChecked=0, Total=1406 [2019-11-27 18:54:26,038 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2019-11-27 18:54:26,066 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 93. [2019-11-27 18:54:26,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2019-11-27 18:54:26,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 112 transitions. [2019-11-27 18:54:26,067 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 112 transitions. Word has length 43 [2019-11-27 18:54:26,068 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-27 18:54:26,068 INFO L462 AbstractCegarLoop]: Abstraction has 93 states and 112 transitions. [2019-11-27 18:54:26,068 INFO L463 AbstractCegarLoop]: Interpolant automaton has 20 states. [2019-11-27 18:54:26,068 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 112 transitions. [2019-11-27 18:54:26,069 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2019-11-27 18:54:26,069 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:54:26,070 INFO L410 BasicCegarLoop]: trace histogram [3, 3, 3, 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] [2019-11-27 18:54:26,275 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 mathsat -unsat_core_generation=3 [2019-11-27 18:54:26,276 INFO L410 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:54:26,276 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:54:26,276 INFO L82 PathProgramCache]: Analyzing trace with hash -1965818131, now seen corresponding path program 2 times [2019-11-27 18:54:26,277 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-27 18:54:26,277 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [195855275] [2019-11-27 18:54:26,277 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 10 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with mathsat -unsat_core_generation=3 [2019-11-27 18:54:26,359 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2019-11-27 18:54:26,359 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-27 18:54:26,365 INFO L255 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 27 conjunts are in the unsatisfiable core [2019-11-27 18:54:26,367 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-27 18:54:26,410 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2019-11-27 18:54:26,411 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:54:26,429 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:54:26,430 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:54:26,430 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:26, output treesize:22 [2019-11-27 18:54:26,707 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:54:26,715 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:54:26,716 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 70 treesize of output 32 [2019-11-27 18:54:26,717 INFO L508 ElimStorePlain]: Start of recursive call 2: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-27 18:54:27,138 WARN L192 SmtUtils]: Spent 421.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 29 [2019-11-27 18:54:27,139 INFO L588 ElimStorePlain]: treesize reduction 3, result has 94.9 percent of original size [2019-11-27 18:54:27,139 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2019-11-27 18:54:27,139 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:87, output treesize:56 [2019-11-27 18:54:27,653 WARN L192 SmtUtils]: Spent 200.00 ms on a formula simplification that was a NOOP. DAG size: 31 [2019-11-27 18:54:28,218 WARN L192 SmtUtils]: Spent 259.00 ms on a formula simplification that was a NOOP. DAG size: 35 [2019-11-27 18:54:28,220 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:54:28,480 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2019-11-27 18:54:28,480 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-27 18:54:29,398 WARN L192 SmtUtils]: Spent 444.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2019-11-27 18:54:29,802 WARN L192 SmtUtils]: Spent 403.00 ms on a formula simplification that was a NOOP. DAG size: 48 [2019-11-27 18:54:30,657 WARN L192 SmtUtils]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 25 [2019-11-27 18:54:33,778 WARN L192 SmtUtils]: Spent 214.00 ms on a formula simplification that was a NOOP. DAG size: 36 [2019-11-27 18:54:38,801 WARN L192 SmtUtils]: Spent 192.00 ms on a formula simplification that was a NOOP. DAG size: 40 [2019-11-27 18:54:45,450 WARN L192 SmtUtils]: Spent 1.10 s on a formula simplification. DAG size of input: 44 DAG size of output: 41 [2019-11-27 18:54:45,496 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 44 treesize of output 40 [2019-11-27 18:54:45,683 WARN L192 SmtUtils]: Spent 105.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2019-11-27 18:54:45,683 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:54:45,684 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 116 treesize of output 120 [2019-11-27 18:54:45,684 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:54:45,684 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:54:45,685 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:54:45,689 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:54:45,689 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:54:45,690 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:54:45,693 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:54:45,694 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2019-11-27 18:54:45,996 WARN L192 SmtUtils]: Spent 301.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 9 [2019-11-27 18:54:45,997 INFO L588 ElimStorePlain]: treesize reduction 196, result has 4.9 percent of original size [2019-11-27 18:54:45,997 INFO L508 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:54:46,088 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:54:46,089 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:54:46,089 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:52, output treesize:18 [2019-11-27 18:54:47,094 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2019-11-27 18:54:47,095 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [195855275] [2019-11-27 18:54:47,095 INFO L220 FreeRefinementEngine]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2019-11-27 18:54:47,095 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12, 10] imperfect sequences [] total 20 [2019-11-27 18:54:47,095 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1732876696] [2019-11-27 18:54:47,096 INFO L442 AbstractCegarLoop]: Interpolant automaton has 20 states [2019-11-27 18:54:47,096 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-27 18:54:47,096 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2019-11-27 18:54:47,096 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=325, Unknown=5, NotChecked=0, Total=380 [2019-11-27 18:54:47,097 INFO L87 Difference]: Start difference. First operand 93 states and 112 transitions. Second operand 20 states. [2019-11-27 18:55:15,635 WARN L192 SmtUtils]: Spent 25.24 s on a formula simplification. DAG size of input: 54 DAG size of output: 51 [2019-11-27 18:55:35,930 WARN L192 SmtUtils]: Spent 19.35 s on a formula simplification. DAG size of input: 62 DAG size of output: 48 [2019-11-27 18:56:03,693 WARN L192 SmtUtils]: Spent 26.43 s on a formula simplification. DAG size of input: 69 DAG size of output: 66 [2019-11-27 18:56:05,862 WARN L192 SmtUtils]: Spent 203.00 ms on a formula simplification that was a NOOP. DAG size: 35 [2019-11-27 18:56:07,908 WARN L192 SmtUtils]: Spent 745.00 ms on a formula simplification that was a NOOP. DAG size: 52 [2019-11-27 18:56:09,646 WARN L192 SmtUtils]: Spent 661.00 ms on a formula simplification that was a NOOP. DAG size: 55 [2019-11-27 18:56:12,588 WARN L192 SmtUtils]: Spent 197.00 ms on a formula simplification that was a NOOP. DAG size: 38 [2019-11-27 18:56:13,825 WARN L192 SmtUtils]: Spent 178.00 ms on a formula simplification that was a NOOP. DAG size: 38 [2019-11-27 18:56:15,314 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-27 18:56:15,314 INFO L93 Difference]: Finished difference Result 108 states and 127 transitions. [2019-11-27 18:56:15,315 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2019-11-27 18:56:15,315 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 41 [2019-11-27 18:56:15,315 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-27 18:56:15,316 INFO L225 Difference]: With dead ends: 108 [2019-11-27 18:56:15,316 INFO L226 Difference]: Without dead ends: 106 [2019-11-27 18:56:15,317 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 63 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 131 ImplicationChecksByTransitivity, 98.5s TimeCoverageRelationStatistics Valid=159, Invalid=828, Unknown=5, NotChecked=0, Total=992 [2019-11-27 18:56:15,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2019-11-27 18:56:15,331 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 94. [2019-11-27 18:56:15,331 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 94 states. [2019-11-27 18:56:15,332 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 113 transitions. [2019-11-27 18:56:15,333 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 113 transitions. Word has length 41 [2019-11-27 18:56:15,333 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-27 18:56:15,333 INFO L462 AbstractCegarLoop]: Abstraction has 94 states and 113 transitions. [2019-11-27 18:56:15,333 INFO L463 AbstractCegarLoop]: Interpolant automaton has 20 states. [2019-11-27 18:56:15,334 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 113 transitions. [2019-11-27 18:56:15,336 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2019-11-27 18:56:15,336 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:56:15,336 INFO L410 BasicCegarLoop]: trace histogram [7, 7, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-27 18:56:15,547 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 mathsat -unsat_core_generation=3 [2019-11-27 18:56:15,548 INFO L410 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:56:15,548 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:56:15,548 INFO L82 PathProgramCache]: Analyzing trace with hash -1957545511, now seen corresponding path program 1 times [2019-11-27 18:56:15,549 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-27 18:56:15,550 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [273034205] [2019-11-27 18:56:15,550 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 11 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with mathsat -unsat_core_generation=3 [2019-11-27 18:56:15,701 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-27 18:56:15,721 INFO L255 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 19 conjunts are in the unsatisfiable core [2019-11-27 18:56:15,724 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-27 18:56:15,806 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:56:16,768 INFO L134 CoverageAnalysis]: Checked inductivity of 124 backedges. 14 proven. 27 refuted. 0 times theorem prover too weak. 83 trivial. 0 not checked. [2019-11-27 18:56:16,768 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-27 18:56:17,067 WARN L192 SmtUtils]: Spent 266.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-27 18:56:17,283 WARN L192 SmtUtils]: Spent 215.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-27 18:56:17,650 WARN L192 SmtUtils]: Spent 359.00 ms on a formula simplification that was a NOOP. DAG size: 26 [2019-11-27 18:56:17,828 WARN L192 SmtUtils]: Spent 177.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2019-11-27 18:56:18,909 WARN L192 SmtUtils]: Spent 1.08 s on a formula simplification that was a NOOP. DAG size: 24 [2019-11-27 18:56:19,595 WARN L192 SmtUtils]: Spent 685.00 ms on a formula simplification that was a NOOP. DAG size: 24 [2019-11-27 18:56:21,215 WARN L192 SmtUtils]: Spent 124.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2019-11-27 18:56:26,295 WARN L192 SmtUtils]: Spent 569.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-27 18:56:26,592 WARN L192 SmtUtils]: Spent 255.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-27 18:56:26,844 WARN L192 SmtUtils]: Spent 251.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-27 18:56:34,968 WARN L192 SmtUtils]: Spent 935.00 ms on a formula simplification that was a NOOP. DAG size: 25 [2019-11-27 18:56:34,969 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:56:40,171 WARN L192 SmtUtils]: Spent 169.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2019-11-27 18:56:48,644 WARN L192 SmtUtils]: Spent 858.00 ms on a formula simplification that was a NOOP. DAG size: 27 [2019-11-27 18:56:50,744 WARN L860 $PredicateComparison]: unable to prove that (let ((.cse1 (bvsdiv (bvadd |c_downsweep_#in~right| (_ bv1 32)) (_ bv2 32)))) (or (let ((.cse0 (bvadd .cse1 (_ bv4294967295 32)))) (bvsgt .cse0 (bvadd .cse1 (bvneg (bvsdiv (bvadd (bvneg .cse0) |c_downsweep_#in~right|) (_ bv2 32)))))) (not (= (bvadd |c_downsweep_#in~left| (_ bv1 32)) .cse1)) (not (bvsgt |c_downsweep_#in~left| (bvadd |c_downsweep_#in~left| (bvneg (bvsdiv (bvadd (bvneg |c_downsweep_#in~left|) |c_downsweep_#in~right|) (_ bv2 32))) (_ bv1 32)))))) is different from true [2019-11-27 18:56:53,512 WARN L192 SmtUtils]: Spent 519.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2019-11-27 18:56:56,449 WARN L192 SmtUtils]: Spent 377.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2019-11-27 18:56:59,846 WARN L192 SmtUtils]: Spent 449.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2019-11-27 18:57:03,235 WARN L192 SmtUtils]: Spent 786.00 ms on a formula simplification that was a NOOP. DAG size: 26 [2019-11-27 18:57:03,288 INFO L134 CoverageAnalysis]: Checked inductivity of 124 backedges. 14 proven. 28 refuted. 6 times theorem prover too weak. 76 trivial. 0 not checked. [2019-11-27 18:57:03,289 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [273034205] [2019-11-27 18:57:03,289 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-27 18:57:03,289 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 13] total 22 [2019-11-27 18:57:03,289 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1028428651] [2019-11-27 18:57:03,289 INFO L442 AbstractCegarLoop]: Interpolant automaton has 22 states [2019-11-27 18:57:03,290 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-27 18:57:03,290 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2019-11-27 18:57:03,290 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=355, Unknown=6, NotChecked=38, Total=462 [2019-11-27 18:57:03,290 INFO L87 Difference]: Start difference. First operand 94 states and 113 transitions. Second operand 22 states. [2019-11-27 18:57:06,037 WARN L192 SmtUtils]: Spent 292.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 24 [2019-11-27 18:57:10,242 WARN L192 SmtUtils]: Spent 1.45 s on a formula simplification. DAG size of input: 37 DAG size of output: 37 [2019-11-27 18:57:13,448 WARN L192 SmtUtils]: Spent 620.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 32 [2019-11-27 18:57:18,176 WARN L192 SmtUtils]: Spent 1.22 s on a formula simplification. DAG size of input: 23 DAG size of output: 21 [2019-11-27 18:57:20,626 WARN L192 SmtUtils]: Spent 538.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 40 [2019-11-27 18:57:24,569 WARN L192 SmtUtils]: Spent 845.00 ms on a formula simplification that was a NOOP. DAG size: 31 [2019-11-27 18:57:43,122 WARN L192 SmtUtils]: Spent 8.65 s on a formula simplification that was a NOOP. DAG size: 30 [2019-11-27 18:58:05,310 WARN L192 SmtUtils]: Spent 17.89 s on a formula simplification that was a NOOP. DAG size: 41 [2019-11-27 18:58:40,583 WARN L192 SmtUtils]: Spent 4.52 s on a formula simplification. DAG size of input: 37 DAG size of output: 24 [2019-11-27 18:59:11,189 WARN L192 SmtUtils]: Spent 6.94 s on a formula simplification. DAG size of input: 31 DAG size of output: 10 [2019-11-27 18:59:15,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-27 18:59:15,869 INFO L93 Difference]: Finished difference Result 143 states and 172 transitions. [2019-11-27 18:59:15,892 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2019-11-27 18:59:15,892 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 76 [2019-11-27 18:59:15,893 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-27 18:59:15,895 INFO L225 Difference]: With dead ends: 143 [2019-11-27 18:59:15,895 INFO L226 Difference]: Without dead ends: 131 [2019-11-27 18:59:15,896 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 130 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 100 ImplicationChecksByTransitivity, 119.1s TimeCoverageRelationStatistics Valid=165, Invalid=825, Unknown=6, NotChecked=60, Total=1056 [2019-11-27 18:59:15,896 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2019-11-27 18:59:15,916 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 115. [2019-11-27 18:59:15,916 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 115 states. [2019-11-27 18:59:15,917 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 142 transitions. [2019-11-27 18:59:15,917 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 142 transitions. Word has length 76 [2019-11-27 18:59:15,918 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-27 18:59:15,918 INFO L462 AbstractCegarLoop]: Abstraction has 115 states and 142 transitions. [2019-11-27 18:59:15,918 INFO L463 AbstractCegarLoop]: Interpolant automaton has 22 states. [2019-11-27 18:59:15,918 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 142 transitions. [2019-11-27 18:59:15,919 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2019-11-27 18:59:15,920 INFO L402 BasicCegarLoop]: Found error trace [2019-11-27 18:59:15,920 INFO L410 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 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] [2019-11-27 18:59:16,122 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 mathsat -unsat_core_generation=3 [2019-11-27 18:59:16,123 INFO L410 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-27 18:59:16,123 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-27 18:59:16,123 INFO L82 PathProgramCache]: Analyzing trace with hash 653476761, now seen corresponding path program 2 times [2019-11-27 18:59:16,124 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-27 18:59:16,124 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1186641635] [2019-11-27 18:59:16,125 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 12 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with mathsat -unsat_core_generation=3 [2019-11-27 18:59:16,346 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-27 18:59:16,346 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-27 18:59:16,370 INFO L255 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 77 conjunts are in the unsatisfiable core [2019-11-27 18:59:16,372 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-27 18:59:16,446 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:59:16,710 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2019-11-27 18:59:16,711 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-27 18:59:16,734 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:59:16,735 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:59:16,735 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:39, output treesize:35 [2019-11-27 18:59:19,141 WARN L192 SmtUtils]: Spent 389.00 ms on a formula simplification that was a NOOP. DAG size: 39 [2019-11-27 18:59:21,164 WARN L860 $PredicateComparison]: unable to prove that (exists ((downsweep_~tmp~0 (_ BitVec 32))) (= |c_#memory_int| (store |c_old(#memory_int)| |c_downsweep_#in~a.base| (let ((.cse2 (bvadd (bvmul |c_downsweep_#in~left| (_ bv4 32)) |c_downsweep_#in~a.offset|))) (store (let ((.cse0 (select |c_old(#memory_int)| |c_downsweep_#in~a.base|)) (.cse1 (bvadd |c_downsweep_#in~a.offset| (bvmul |c_downsweep_#in~right| (_ bv4 32))))) (store .cse0 .cse1 (bvadd (select .cse0 .cse2) (select .cse0 .cse1)))) .cse2 downsweep_~tmp~0))))) is different from true [2019-11-27 18:59:23,391 WARN L860 $PredicateComparison]: unable to prove that (exists ((downsweep_~tmp~0 (_ BitVec 32))) (= (store |c_old(#memory_int)| |c_downsweep_#in~a.base| (let ((.cse9 (bvmul (bvneg (bvsdiv (bvadd (bvneg |c_downsweep_#in~left|) |c_downsweep_#in~right|) (_ bv2 32))) (_ bv4 32))) (.cse10 (bvmul |c_downsweep_#in~right| (_ bv4 32)))) (let ((.cse2 (bvadd .cse9 |c_downsweep_#in~a.offset| .cse10))) (store (let ((.cse1 (bvadd |c_downsweep_#in~a.offset| .cse10))) (let ((.cse0 (let ((.cse7 (select |c_old(#memory_int)| |c_downsweep_#in~a.base|)) (.cse8 (bvmul |c_downsweep_#in~left| (_ bv4 32)))) (let ((.cse6 (bvadd .cse9 .cse8 |c_downsweep_#in~a.offset|)) (.cse5 (select .cse7 .cse1))) (store (let ((.cse4 (bvadd .cse8 |c_downsweep_#in~a.offset|))) (let ((.cse3 (store .cse7 .cse1 (bvadd (select .cse7 .cse4) .cse5)))) (store .cse3 .cse4 (bvadd (select (store .cse3 .cse4 .cse5) .cse6) .cse5)))) .cse6 .cse5))))) (store .cse0 .cse1 (bvadd (select .cse0 .cse1) (select .cse0 .cse2))))) .cse2 downsweep_~tmp~0)))) |c_#memory_int|)) is different from true [2019-11-27 18:59:23,399 INFO L377 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 559 treesize of output 502 [2019-11-27 18:59:23,428 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,469 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,510 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,549 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,591 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,610 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,654 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,696 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,715 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,736 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,778 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,818 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,841 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,882 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,923 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:23,963 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:24,006 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:24,027 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-27 18:59:24,027 INFO L237 Elim1Store]: Index analysis took 206 ms [2019-11-27 18:59:24,029 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 185 treesize of output 89 [2019-11-27 18:59:24,030 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-27 18:59:24,336 WARN L192 SmtUtils]: Spent 306.00 ms on a formula simplification that was a NOOP. DAG size: 27 [2019-11-27 18:59:24,337 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:59:24,337 INFO L508 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-27 18:59:24,813 WARN L192 SmtUtils]: Spent 475.00 ms on a formula simplification that was a NOOP. DAG size: 36 [2019-11-27 18:59:24,814 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-27 18:59:24,814 INFO L508 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-27 18:59:24,815 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:581, output treesize:51 [2019-11-27 18:59:25,880 WARN L192 SmtUtils]: Spent 135.00 ms on a formula simplification that was a NOOP. DAG size: 33 [2019-11-27 18:59:26,872 WARN L192 SmtUtils]: Spent 220.00 ms on a formula simplification that was a NOOP. DAG size: 37 [2019-11-27 18:59:26,873 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:59:27,189 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 17 trivial. 8 not checked. [2019-11-27 18:59:27,189 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-27 18:59:28,589 WARN L192 SmtUtils]: Spent 516.00 ms on a formula simplification that was a NOOP. DAG size: 46 [2019-11-27 18:59:29,063 WARN L192 SmtUtils]: Spent 473.00 ms on a formula simplification that was a NOOP. DAG size: 44 [2019-11-27 18:59:29,644 WARN L192 SmtUtils]: Spent 476.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2019-11-27 18:59:30,093 WARN L192 SmtUtils]: Spent 448.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2019-11-27 18:59:32,835 WARN L192 SmtUtils]: Spent 2.74 s on a formula simplification that was a NOOP. DAG size: 104 [2019-11-27 18:59:33,558 WARN L192 SmtUtils]: Spent 720.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2019-11-27 18:59:35,361 WARN L192 SmtUtils]: Spent 1.80 s on a formula simplification that was a NOOP. DAG size: 65 [2019-11-27 18:59:36,835 WARN L192 SmtUtils]: Spent 1.47 s on a formula simplification that was a NOOP. DAG size: 63 [2019-11-27 18:59:45,463 WARN L192 SmtUtils]: Spent 473.00 ms on a formula simplification that was a NOOP. DAG size: 53 [2019-11-27 18:59:45,914 WARN L192 SmtUtils]: Spent 348.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2019-11-27 18:59:46,213 WARN L192 SmtUtils]: Spent 298.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2019-11-27 18:59:56,786 WARN L192 SmtUtils]: Spent 1.05 s on a formula simplification that was a NOOP. DAG size: 72 [2019-11-27 18:59:56,789 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-27 18:59:56,994 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 mathsat -unsat_core_generation=3 [2019-11-27 18:59:56,996 FATAL L? ?]: The Plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction has thrown an exception: java.lang.AssertionError: Alternating quantifiers not yet supported at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.applyComplexEliminationRules(ElimStorePlain.java:283) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.doElimOneRec(ElimStorePlain.java:264) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.eliminateOne(ElimStorePlain.java:565) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.doElimAllRec(ElimStorePlain.java:478) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.startRecursiveElimination(ElimStorePlain.java:216) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.PartialQuantifierElimination.elim(PartialQuantifierElimination.java:306) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.PartialQuantifierElimination.tryToEliminate(PartialQuantifierElimination.java:102) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer$QuantifierEliminationPostprocessor.postprocess(IterativePredicateTransformer.java:246) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.applyPostprocessors(IterativePredicateTransformer.java:440) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.computeBackwardSequence(IterativePredicateTransformer.java:419) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.computeWeakestPreconditionSequence(IterativePredicateTransformer.java:291) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolantsUsingUnsatCore(TraceCheckSpWp.java:334) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolants(TraceCheckSpWp.java:177) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.(TraceCheckSpWp.java:162) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:108) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:1) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.isCorrect(IpTcStrategyModuleBase.java:57) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.checkFeasibility(AutomatonFreeRefinementEngine.java:242) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:166) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:75) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:463) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterateInternal(AbstractCegarLoop.java:419) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:368) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopResult.iterate(CegarLoopResult.java:139) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.iterateNew(TraceAbstractionStarter.java:332) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:174) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:126) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:120) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:316) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:55) [2019-11-27 18:59:57,000 INFO L168 Benchmark]: Toolchain (without parser) took 750352.53 ms. Allocated memory was 1.0 GB in the beginning and 1.2 GB in the end (delta: 211.8 MB). Free memory was 960.4 MB in the beginning and 1.1 GB in the end (delta: -188.6 MB). Peak memory consumption was 23.2 MB. Max. memory is 11.5 GB. [2019-11-27 18:59:57,001 INFO L168 Benchmark]: CDTParser took 0.14 ms. Allocated memory is still 1.0 GB. Free memory is still 987.2 MB. There was no memory consumed. Max. memory is 11.5 GB. [2019-11-27 18:59:57,002 INFO L168 Benchmark]: CACSL2BoogieTranslator took 289.35 ms. Allocated memory is still 1.0 GB. Free memory was 960.4 MB in the beginning and 949.6 MB in the end (delta: 10.7 MB). Peak memory consumption was 10.7 MB. Max. memory is 11.5 GB. [2019-11-27 18:59:57,002 INFO L168 Benchmark]: Boogie Procedure Inliner took 132.03 ms. Allocated memory was 1.0 GB in the beginning and 1.2 GB in the end (delta: 127.4 MB). Free memory was 949.6 MB in the beginning and 1.1 GB in the end (delta: -167.5 MB). Peak memory consumption was 15.2 MB. Max. memory is 11.5 GB. [2019-11-27 18:59:57,002 INFO L168 Benchmark]: Boogie Preprocessor took 33.11 ms. Allocated memory is still 1.2 GB. Free memory is still 1.1 GB. There was no memory consumed. Max. memory is 11.5 GB. [2019-11-27 18:59:57,003 INFO L168 Benchmark]: RCFGBuilder took 476.69 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 26.9 MB). Peak memory consumption was 26.9 MB. Max. memory is 11.5 GB. [2019-11-27 18:59:57,003 INFO L168 Benchmark]: TraceAbstraction took 749416.32 ms. Allocated memory was 1.2 GB in the beginning and 1.2 GB in the end (delta: 84.4 MB). Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: -58.7 MB). Peak memory consumption was 25.7 MB. Max. memory is 11.5 GB. [2019-11-27 18:59:57,005 INFO L335 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.14 ms. Allocated memory is still 1.0 GB. Free memory is still 987.2 MB. There was no memory consumed. Max. memory is 11.5 GB. * CACSL2BoogieTranslator took 289.35 ms. Allocated memory is still 1.0 GB. Free memory was 960.4 MB in the beginning and 949.6 MB in the end (delta: 10.7 MB). Peak memory consumption was 10.7 MB. Max. memory is 11.5 GB. * Boogie Procedure Inliner took 132.03 ms. Allocated memory was 1.0 GB in the beginning and 1.2 GB in the end (delta: 127.4 MB). Free memory was 949.6 MB in the beginning and 1.1 GB in the end (delta: -167.5 MB). Peak memory consumption was 15.2 MB. Max. memory is 11.5 GB. * Boogie Preprocessor took 33.11 ms. Allocated memory is still 1.2 GB. Free memory is still 1.1 GB. There was no memory consumed. Max. memory is 11.5 GB. * RCFGBuilder took 476.69 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 26.9 MB). Peak memory consumption was 26.9 MB. Max. memory is 11.5 GB. * TraceAbstraction took 749416.32 ms. Allocated memory was 1.2 GB in the beginning and 1.2 GB in the end (delta: 84.4 MB). Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: -58.7 MB). Peak memory consumption was 25.7 MB. Max. memory is 11.5 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: AssertionError: Alternating quantifiers not yet supported de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: AssertionError: Alternating quantifiers not yet supported: de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.applyComplexEliminationRules(ElimStorePlain.java:283) RESULT: Ultimate could not prove your program: Toolchain returned no result. Received shutdown request...