/usr/bin/java -ea -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/verifythis/lcp.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-07 12:29:25,232 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-07 12:29:25,233 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-07 12:29:25,260 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-07 12:29:25,261 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-07 12:29:25,262 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-07 12:29:25,265 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-07 12:29:25,269 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-07 12:29:25,271 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-07 12:29:25,275 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-07 12:29:25,276 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-07 12:29:25,276 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-07 12:29:25,276 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-07 12:29:25,277 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-07 12:29:25,277 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-07 12:29:25,278 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-07 12:29:25,278 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-07 12:29:25,279 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-07 12:29:25,280 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-07 12:29:25,281 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-07 12:29:25,281 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-07 12:29:25,284 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-07 12:29:25,285 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-07 12:29:25,286 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-07 12:29:25,287 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-07 12:29:25,295 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-07 12:29:25,295 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-07 12:29:25,295 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-07 12:29:25,296 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-07 12:29:25,296 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-07 12:29:25,297 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-07 12:29:25,297 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-07 12:29:25,298 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-07 12:29:25,299 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-07 12:29:25,299 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-07 12:29:25,299 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-07 12:29:25,300 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-07 12:29:25,300 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-07 12:29:25,300 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-07 12:29:25,300 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-07 12:29:25,301 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-07 12:29:25,302 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-07 12:29:25,303 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2022-04-07 12:29:25,328 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-07 12:29:25,328 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-07 12:29:25,328 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-04-07 12:29:25,328 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-04-07 12:29:25,329 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-07 12:29:25,329 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-07 12:29:25,329 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-07 12:29:25,329 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-07 12:29:25,329 INFO L138 SettingsManager]: * Use SBE=true [2022-04-07 12:29:25,330 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-07 12:29:25,330 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-07 12:29:25,330 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-07 12:29:25,330 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-07 12:29:25,330 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-07 12:29:25,330 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-07 12:29:25,330 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-07 12:29:25,330 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-07 12:29:25,330 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-07 12:29:25,330 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-07 12:29:25,330 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-07 12:29:25,331 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-07 12:29:25,331 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-07 12:29:25,331 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-07 12:29:25,331 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-07 12:29:25,331 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-07 12:29:25,331 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-07 12:29:25,331 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-07 12:29:25,331 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-07 12:29:25,331 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-07 12:29:25,331 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-07 12:29:25,332 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2022-04-07 12:29:25,332 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-04-07 12:29:25,332 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-07 12:29:25,332 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-07 12:29:25,498 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-07 12:29:25,512 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-07 12:29:25,514 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-07 12:29:25,515 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-07 12:29:25,516 INFO L275 PluginConnector]: CDTParser initialized [2022-04-07 12:29:25,517 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/verifythis/lcp.c [2022-04-07 12:29:25,575 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0ad27c5da/ca619a073ab64a83bae56c7c76ce89da/FLAGcb3eacf49 [2022-04-07 12:29:25,958 INFO L306 CDTParser]: Found 1 translation units. [2022-04-07 12:29:25,959 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/verifythis/lcp.c [2022-04-07 12:29:25,965 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0ad27c5da/ca619a073ab64a83bae56c7c76ce89da/FLAGcb3eacf49 [2022-04-07 12:29:25,976 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0ad27c5da/ca619a073ab64a83bae56c7c76ce89da [2022-04-07 12:29:25,978 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-07 12:29:25,980 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-07 12:29:25,981 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-07 12:29:25,981 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-07 12:29:25,984 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-07 12:29:25,988 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.04 12:29:25" (1/1) ... [2022-04-07 12:29:25,989 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@739bbba6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:29:25, skipping insertion in model container [2022-04-07 12:29:25,989 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.04 12:29:25" (1/1) ... [2022-04-07 12:29:25,993 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-07 12:29:26,002 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-07 12:29:26,118 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/verifythis/lcp.c[515,528] [2022-04-07 12:29:26,147 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-07 12:29:26,153 INFO L203 MainTranslator]: Completed pre-run [2022-04-07 12:29:26,165 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/verifythis/lcp.c[515,528] [2022-04-07 12:29:26,173 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-07 12:29:26,184 INFO L208 MainTranslator]: Completed translation [2022-04-07 12:29:26,185 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:29:26 WrapperNode [2022-04-07 12:29:26,185 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-07 12:29:26,185 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-07 12:29:26,186 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-07 12:29:26,186 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-07 12:29:26,192 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:29:26" (1/1) ... [2022-04-07 12:29:26,192 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:29:26" (1/1) ... [2022-04-07 12:29:26,197 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:29:26" (1/1) ... [2022-04-07 12:29:26,197 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:29:26" (1/1) ... [2022-04-07 12:29:26,207 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:29:26" (1/1) ... [2022-04-07 12:29:26,211 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:29:26" (1/1) ... [2022-04-07 12:29:26,211 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:29:26" (1/1) ... [2022-04-07 12:29:26,213 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-07 12:29:26,213 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-07 12:29:26,213 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-07 12:29:26,214 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-07 12:29:26,214 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:29:26" (1/1) ... [2022-04-07 12:29:26,218 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-07 12:29:26,224 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 12:29:26,232 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-07 12:29:26,233 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-07 12:29:26,255 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-07 12:29:26,255 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-07 12:29:26,255 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-07 12:29:26,256 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-07 12:29:26,256 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-07 12:29:26,256 INFO L138 BoogieDeclarations]: Found implementation of procedure lcp [2022-04-07 12:29:26,256 INFO L138 BoogieDeclarations]: Found implementation of procedure check [2022-04-07 12:29:26,256 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-07 12:29:26,256 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.meminit [2022-04-07 12:29:26,256 INFO L130 BoogieDeclarations]: Found specification of procedure calloc [2022-04-07 12:29:26,256 INFO L130 BoogieDeclarations]: Found specification of procedure free [2022-04-07 12:29:26,256 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-07 12:29:26,256 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-07 12:29:26,256 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure lcp [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure check [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.meminit [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-07 12:29:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-07 12:29:26,258 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-07 12:29:26,258 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-07 12:29:26,258 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-07 12:29:26,311 INFO L234 CfgBuilder]: Building ICFG [2022-04-07 12:29:26,312 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-07 12:29:26,465 INFO L275 CfgBuilder]: Performing block encoding [2022-04-07 12:29:26,470 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-07 12:29:26,470 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-07 12:29:26,471 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.04 12:29:26 BoogieIcfgContainer [2022-04-07 12:29:26,471 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-07 12:29:26,472 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-07 12:29:26,472 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-07 12:29:26,474 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-07 12:29:26,474 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 07.04 12:29:25" (1/3) ... [2022-04-07 12:29:26,475 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6a9e75fb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.04 12:29:26, skipping insertion in model container [2022-04-07 12:29:26,475 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:29:26" (2/3) ... [2022-04-07 12:29:26,475 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6a9e75fb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.04 12:29:26, skipping insertion in model container [2022-04-07 12:29:26,475 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.04 12:29:26" (3/3) ... [2022-04-07 12:29:26,476 INFO L111 eAbstractionObserver]: Analyzing ICFG lcp.c [2022-04-07 12:29:26,479 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-07 12:29:26,479 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-07 12:29:26,506 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-07 12:29:26,513 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-07 12:29:26,513 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-07 12:29:26,526 INFO L276 IsEmpty]: Start isEmpty. Operand has 49 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 31 states have internal predecessors, (37), 10 states have call successors, (10), 7 states have call predecessors, (10), 7 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-07 12:29:26,530 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2022-04-07 12:29:26,530 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 12:29:26,530 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 12:29:26,531 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 12:29:26,534 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 12:29:26,534 INFO L85 PathProgramCache]: Analyzing trace with hash -675162514, now seen corresponding path program 1 times [2022-04-07 12:29:26,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 12:29:26,540 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [681358341] [2022-04-07 12:29:26,540 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 12:29:26,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 12:29:26,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:26,697 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-07 12:29:26,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:26,722 INFO L290 TraceCheckUtils]: 0: Hoare triple {77#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {52#true} is VALID [2022-04-07 12:29:26,722 INFO L290 TraceCheckUtils]: 1: Hoare triple {52#true} assume true; {52#true} is VALID [2022-04-07 12:29:26,722 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {52#true} {52#true} #91#return; {52#true} is VALID [2022-04-07 12:29:26,723 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-07 12:29:26,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:26,735 INFO L290 TraceCheckUtils]: 0: Hoare triple {52#true} ~cond := #in~cond; {52#true} is VALID [2022-04-07 12:29:26,736 INFO L290 TraceCheckUtils]: 1: Hoare triple {52#true} assume 0 == ~cond;assume false; {53#false} is VALID [2022-04-07 12:29:26,736 INFO L290 TraceCheckUtils]: 2: Hoare triple {53#false} assume true; {53#false} is VALID [2022-04-07 12:29:26,737 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {53#false} {52#true} #75#return; {53#false} is VALID [2022-04-07 12:29:26,743 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-07 12:29:26,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:26,765 INFO L290 TraceCheckUtils]: 0: Hoare triple {78#(= |#memory_int| |old(#memory_int)|)} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {52#true} is VALID [2022-04-07 12:29:26,765 INFO L290 TraceCheckUtils]: 1: Hoare triple {52#true} assume true; {52#true} is VALID [2022-04-07 12:29:26,765 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {52#true} {53#false} #77#return; {53#false} is VALID [2022-04-07 12:29:26,765 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-07 12:29:26,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:26,772 INFO L290 TraceCheckUtils]: 0: Hoare triple {52#true} ~cond := #in~cond; {52#true} is VALID [2022-04-07 12:29:26,773 INFO L290 TraceCheckUtils]: 1: Hoare triple {52#true} assume 0 == ~cond;assume false; {53#false} is VALID [2022-04-07 12:29:26,773 INFO L290 TraceCheckUtils]: 2: Hoare triple {53#false} assume true; {53#false} is VALID [2022-04-07 12:29:26,773 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {53#false} {53#false} #79#return; {53#false} is VALID [2022-04-07 12:29:26,773 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-04-07 12:29:26,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:26,781 INFO L290 TraceCheckUtils]: 0: Hoare triple {52#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {52#true} is VALID [2022-04-07 12:29:26,782 INFO L290 TraceCheckUtils]: 1: Hoare triple {52#true} assume !true; {53#false} is VALID [2022-04-07 12:29:26,782 INFO L290 TraceCheckUtils]: 2: Hoare triple {53#false} #res := ~l~0; {53#false} is VALID [2022-04-07 12:29:26,782 INFO L290 TraceCheckUtils]: 3: Hoare triple {53#false} assume true; {53#false} is VALID [2022-04-07 12:29:26,783 INFO L284 TraceCheckUtils]: 4: Hoare quadruple {53#false} {53#false} #81#return; {53#false} is VALID [2022-04-07 12:29:26,783 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2022-04-07 12:29:26,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:26,793 INFO L290 TraceCheckUtils]: 0: Hoare triple {52#true} ~cond := #in~cond; {52#true} is VALID [2022-04-07 12:29:26,793 INFO L290 TraceCheckUtils]: 1: Hoare triple {52#true} assume 0 == ~cond;assume false; {53#false} is VALID [2022-04-07 12:29:26,793 INFO L290 TraceCheckUtils]: 2: Hoare triple {53#false} assume true; {53#false} is VALID [2022-04-07 12:29:26,794 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {53#false} {53#false} #85#return; {53#false} is VALID [2022-04-07 12:29:26,795 INFO L272 TraceCheckUtils]: 0: Hoare triple {52#true} call ULTIMATE.init(); {77#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-07 12:29:26,795 INFO L290 TraceCheckUtils]: 1: Hoare triple {77#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {52#true} is VALID [2022-04-07 12:29:26,796 INFO L290 TraceCheckUtils]: 2: Hoare triple {52#true} assume true; {52#true} is VALID [2022-04-07 12:29:26,796 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {52#true} {52#true} #91#return; {52#true} is VALID [2022-04-07 12:29:26,797 INFO L272 TraceCheckUtils]: 4: Hoare triple {52#true} call #t~ret19 := main(); {52#true} is VALID [2022-04-07 12:29:26,797 INFO L290 TraceCheckUtils]: 5: Hoare triple {52#true} assume -2147483648 <= #t~nondet14 && #t~nondet14 <= 2147483647;~n~0 := #t~nondet14;havoc #t~nondet14; {52#true} is VALID [2022-04-07 12:29:26,798 INFO L272 TraceCheckUtils]: 6: Hoare triple {52#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 < 1073741824 then 1 else 0)); {52#true} is VALID [2022-04-07 12:29:26,798 INFO L290 TraceCheckUtils]: 7: Hoare triple {52#true} ~cond := #in~cond; {52#true} is VALID [2022-04-07 12:29:26,798 INFO L290 TraceCheckUtils]: 8: Hoare triple {52#true} assume 0 == ~cond;assume false; {53#false} is VALID [2022-04-07 12:29:26,798 INFO L290 TraceCheckUtils]: 9: Hoare triple {53#false} assume true; {53#false} is VALID [2022-04-07 12:29:26,799 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {53#false} {52#true} #75#return; {53#false} is VALID [2022-04-07 12:29:26,799 INFO L290 TraceCheckUtils]: 11: Hoare triple {53#false} call #t~malloc15.base, #t~malloc15.offset := #Ultimate.allocOnHeap(4 * ~n~0); {53#false} is VALID [2022-04-07 12:29:26,799 INFO L272 TraceCheckUtils]: 12: Hoare triple {53#false} call #Ultimate.meminit(#t~malloc15.base, #t~malloc15.offset, ~n~0, 4, 4 * ~n~0); {78#(= |#memory_int| |old(#memory_int)|)} is VALID [2022-04-07 12:29:26,799 INFO L290 TraceCheckUtils]: 13: Hoare triple {78#(= |#memory_int| |old(#memory_int)|)} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {52#true} is VALID [2022-04-07 12:29:26,799 INFO L290 TraceCheckUtils]: 14: Hoare triple {52#true} assume true; {52#true} is VALID [2022-04-07 12:29:26,799 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {52#true} {53#false} #77#return; {53#false} is VALID [2022-04-07 12:29:26,800 INFO L290 TraceCheckUtils]: 16: Hoare triple {53#false} ~a~0.base, ~a~0.offset := #t~malloc15.base, #t~malloc15.offset;assume -2147483648 <= #t~nondet16 && #t~nondet16 <= 2147483647;~x~0 := #t~nondet16;havoc #t~nondet16;assume -2147483648 <= #t~nondet17 && #t~nondet17 <= 2147483647;~y~0 := #t~nondet17;havoc #t~nondet17; {53#false} is VALID [2022-04-07 12:29:26,800 INFO L272 TraceCheckUtils]: 17: Hoare triple {53#false} call assume_abort_if_not((if ~x~0 >= 0 && ~y~0 >= 0 then 1 else 0)); {52#true} is VALID [2022-04-07 12:29:26,800 INFO L290 TraceCheckUtils]: 18: Hoare triple {52#true} ~cond := #in~cond; {52#true} is VALID [2022-04-07 12:29:26,801 INFO L290 TraceCheckUtils]: 19: Hoare triple {52#true} assume 0 == ~cond;assume false; {53#false} is VALID [2022-04-07 12:29:26,801 INFO L290 TraceCheckUtils]: 20: Hoare triple {53#false} assume true; {53#false} is VALID [2022-04-07 12:29:26,801 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {53#false} {53#false} #79#return; {53#false} is VALID [2022-04-07 12:29:26,801 INFO L272 TraceCheckUtils]: 22: Hoare triple {53#false} call #t~ret18 := lcp(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0); {52#true} is VALID [2022-04-07 12:29:26,801 INFO L290 TraceCheckUtils]: 23: Hoare triple {52#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {52#true} is VALID [2022-04-07 12:29:26,801 INFO L290 TraceCheckUtils]: 24: Hoare triple {52#true} assume !true; {53#false} is VALID [2022-04-07 12:29:26,804 INFO L290 TraceCheckUtils]: 25: Hoare triple {53#false} #res := ~l~0; {53#false} is VALID [2022-04-07 12:29:26,804 INFO L290 TraceCheckUtils]: 26: Hoare triple {53#false} assume true; {53#false} is VALID [2022-04-07 12:29:26,804 INFO L284 TraceCheckUtils]: 27: Hoare quadruple {53#false} {53#false} #81#return; {53#false} is VALID [2022-04-07 12:29:26,804 INFO L290 TraceCheckUtils]: 28: Hoare triple {53#false} assume -2147483648 <= #t~ret18 && #t~ret18 <= 2147483647;~l~1 := #t~ret18;havoc #t~ret18; {53#false} is VALID [2022-04-07 12:29:26,804 INFO L272 TraceCheckUtils]: 29: Hoare triple {53#false} call check(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0, ~l~1); {53#false} is VALID [2022-04-07 12:29:26,805 INFO L290 TraceCheckUtils]: 30: Hoare triple {53#false} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l := #in~l;assume -2147483648 <= #t~nondet9 && #t~nondet9 <= 2147483647;~i~0 := #t~nondet9;havoc #t~nondet9; {53#false} is VALID [2022-04-07 12:29:26,806 INFO L272 TraceCheckUtils]: 31: Hoare triple {53#false} call assume_abort_if_not((if 0 <= ~i~0 && ~i~0 < ~l then 1 else 0)); {52#true} is VALID [2022-04-07 12:29:26,807 INFO L290 TraceCheckUtils]: 32: Hoare triple {52#true} ~cond := #in~cond; {52#true} is VALID [2022-04-07 12:29:26,809 INFO L290 TraceCheckUtils]: 33: Hoare triple {52#true} assume 0 == ~cond;assume false; {53#false} is VALID [2022-04-07 12:29:26,809 INFO L290 TraceCheckUtils]: 34: Hoare triple {53#false} assume true; {53#false} is VALID [2022-04-07 12:29:26,811 INFO L284 TraceCheckUtils]: 35: Hoare quadruple {53#false} {53#false} #85#return; {53#false} is VALID [2022-04-07 12:29:26,811 INFO L290 TraceCheckUtils]: 36: Hoare triple {53#false} call #t~mem10 := read~int(~a.base, ~a.offset + 4 * (~x + ~i~0), 4);call #t~mem11 := read~int(~a.base, ~a.offset + 4 * (~y + ~i~0), 4); {53#false} is VALID [2022-04-07 12:29:26,812 INFO L272 TraceCheckUtils]: 37: Hoare triple {53#false} call __VERIFIER_assert((if #t~mem10 == #t~mem11 then 1 else 0)); {53#false} is VALID [2022-04-07 12:29:26,812 INFO L290 TraceCheckUtils]: 38: Hoare triple {53#false} ~cond := #in~cond; {53#false} is VALID [2022-04-07 12:29:26,812 INFO L290 TraceCheckUtils]: 39: Hoare triple {53#false} assume 0 == ~cond; {53#false} is VALID [2022-04-07 12:29:26,812 INFO L290 TraceCheckUtils]: 40: Hoare triple {53#false} assume !false; {53#false} is VALID [2022-04-07 12:29:26,812 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-07 12:29:26,813 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 12:29:26,813 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [681358341] [2022-04-07 12:29:26,813 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [681358341] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 12:29:26,814 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 12:29:26,814 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-07 12:29:26,815 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [818746313] [2022-04-07 12:29:26,815 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 12:29:26,822 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 5.0) internal successors, (20), 2 states have internal predecessors, (20), 2 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 41 [2022-04-07 12:29:26,824 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 12:29:26,826 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 4 states, 4 states have (on average 5.0) internal successors, (20), 2 states have internal predecessors, (20), 2 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-07 12:29:26,865 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 35 edges. 35 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 12:29:26,865 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-07 12:29:26,865 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 12:29:26,887 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-07 12:29:26,888 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-07 12:29:26,891 INFO L87 Difference]: Start difference. First operand has 49 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 31 states have internal predecessors, (37), 10 states have call successors, (10), 7 states have call predecessors, (10), 7 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 4 states, 4 states have (on average 5.0) internal successors, (20), 2 states have internal predecessors, (20), 2 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-07 12:29:27,175 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:27,175 INFO L93 Difference]: Finished difference Result 91 states and 113 transitions. [2022-04-07 12:29:27,175 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-07 12:29:27,176 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 5.0) internal successors, (20), 2 states have internal predecessors, (20), 2 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 41 [2022-04-07 12:29:27,176 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 12:29:27,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 5.0) internal successors, (20), 2 states have internal predecessors, (20), 2 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-07 12:29:27,195 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 113 transitions. [2022-04-07 12:29:27,196 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 5.0) internal successors, (20), 2 states have internal predecessors, (20), 2 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-07 12:29:27,200 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 113 transitions. [2022-04-07 12:29:27,200 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 113 transitions. [2022-04-07 12:29:27,347 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 113 edges. 113 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 12:29:27,355 INFO L225 Difference]: With dead ends: 91 [2022-04-07 12:29:27,355 INFO L226 Difference]: Without dead ends: 41 [2022-04-07 12:29:27,358 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2022-04-07 12:29:27,361 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 56 mSDsluCounter, 2 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 12:29:27,362 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [59 Valid, 43 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 12:29:27,371 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-04-07 12:29:27,385 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-04-07 12:29:27,385 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 12:29:27,386 INFO L82 GeneralOperation]: Start isEquivalent. First operand 41 states. Second operand has 41 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:27,387 INFO L74 IsIncluded]: Start isIncluded. First operand 41 states. Second operand has 41 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:27,388 INFO L87 Difference]: Start difference. First operand 41 states. Second operand has 41 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:27,393 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:27,394 INFO L93 Difference]: Finished difference Result 41 states and 45 transitions. [2022-04-07 12:29:27,394 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-07 12:29:27,394 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 12:29:27,394 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 12:29:27,394 INFO L74 IsIncluded]: Start isIncluded. First operand has 41 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 41 states. [2022-04-07 12:29:27,395 INFO L87 Difference]: Start difference. First operand has 41 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 41 states. [2022-04-07 12:29:27,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:27,404 INFO L93 Difference]: Finished difference Result 41 states and 45 transitions. [2022-04-07 12:29:27,404 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-07 12:29:27,404 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 12:29:27,404 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 12:29:27,404 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 12:29:27,405 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 12:29:27,405 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:27,410 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 45 transitions. [2022-04-07 12:29:27,411 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 45 transitions. Word has length 41 [2022-04-07 12:29:27,411 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 12:29:27,412 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 45 transitions. [2022-04-07 12:29:27,412 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 5.0) internal successors, (20), 2 states have internal predecessors, (20), 2 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-07 12:29:27,412 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-07 12:29:27,413 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-04-07 12:29:27,413 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 12:29:27,413 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 12:29:27,413 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-07 12:29:27,413 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 12:29:27,414 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 12:29:27,414 INFO L85 PathProgramCache]: Analyzing trace with hash 1025657093, now seen corresponding path program 1 times [2022-04-07 12:29:27,414 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 12:29:27,414 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1561309318] [2022-04-07 12:29:27,415 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 12:29:27,415 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 12:29:27,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:27,563 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-07 12:29:27,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:27,581 INFO L290 TraceCheckUtils]: 0: Hoare triple {376#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {347#true} is VALID [2022-04-07 12:29:27,581 INFO L290 TraceCheckUtils]: 1: Hoare triple {347#true} assume true; {347#true} is VALID [2022-04-07 12:29:27,581 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {347#true} {347#true} #91#return; {347#true} is VALID [2022-04-07 12:29:27,581 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-07 12:29:27,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:27,590 INFO L290 TraceCheckUtils]: 0: Hoare triple {347#true} ~cond := #in~cond; {347#true} is VALID [2022-04-07 12:29:27,591 INFO L290 TraceCheckUtils]: 1: Hoare triple {347#true} assume !(0 == ~cond); {347#true} is VALID [2022-04-07 12:29:27,591 INFO L290 TraceCheckUtils]: 2: Hoare triple {347#true} assume true; {347#true} is VALID [2022-04-07 12:29:27,591 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {347#true} {347#true} #75#return; {347#true} is VALID [2022-04-07 12:29:27,596 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-07 12:29:27,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:27,622 INFO L290 TraceCheckUtils]: 0: Hoare triple {377#(= |#memory_int| |old(#memory_int)|)} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {378#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} is VALID [2022-04-07 12:29:27,623 INFO L290 TraceCheckUtils]: 1: Hoare triple {378#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} assume true; {378#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} is VALID [2022-04-07 12:29:27,624 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {378#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} {347#true} #77#return; {359#(= ((as const (Array Int Int)) 0) (select |#memory_int| |main_#t~malloc15.base|))} is VALID [2022-04-07 12:29:27,624 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-07 12:29:27,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:27,634 INFO L290 TraceCheckUtils]: 0: Hoare triple {347#true} ~cond := #in~cond; {347#true} is VALID [2022-04-07 12:29:27,635 INFO L290 TraceCheckUtils]: 1: Hoare triple {347#true} assume !(0 == ~cond); {347#true} is VALID [2022-04-07 12:29:27,635 INFO L290 TraceCheckUtils]: 2: Hoare triple {347#true} assume true; {347#true} is VALID [2022-04-07 12:29:27,635 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {347#true} {360#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} #79#return; {360#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} is VALID [2022-04-07 12:29:27,636 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-04-07 12:29:27,653 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:27,706 INFO L290 TraceCheckUtils]: 0: Hoare triple {347#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {379#(= |lcp_#in~a.base| lcp_~a.base)} is VALID [2022-04-07 12:29:27,707 INFO L290 TraceCheckUtils]: 1: Hoare triple {379#(= |lcp_#in~a.base| lcp_~a.base)} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {379#(= |lcp_#in~a.base| lcp_~a.base)} is VALID [2022-04-07 12:29:27,708 INFO L290 TraceCheckUtils]: 2: Hoare triple {379#(= |lcp_#in~a.base| lcp_~a.base)} assume #t~short7;call #t~mem5 := read~int(~a.base, ~a.offset + 4 * (~x + ~l~0), 4);call #t~mem6 := read~int(~a.base, ~a.offset + 4 * (~y + ~l~0), 4);#t~short7 := #t~mem5 == #t~mem6; {380#(or |lcp_#t~short7| (not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|))))} is VALID [2022-04-07 12:29:27,709 INFO L290 TraceCheckUtils]: 3: Hoare triple {380#(or |lcp_#t~short7| (not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|))))} assume !#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7; {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} is VALID [2022-04-07 12:29:27,709 INFO L290 TraceCheckUtils]: 4: Hoare triple {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} #res := ~l~0; {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} is VALID [2022-04-07 12:29:27,709 INFO L290 TraceCheckUtils]: 5: Hoare triple {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} assume true; {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} is VALID [2022-04-07 12:29:27,711 INFO L284 TraceCheckUtils]: 6: Hoare quadruple {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} {360#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} #81#return; {348#false} is VALID [2022-04-07 12:29:27,711 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2022-04-07 12:29:27,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:27,717 INFO L290 TraceCheckUtils]: 0: Hoare triple {347#true} ~cond := #in~cond; {347#true} is VALID [2022-04-07 12:29:27,717 INFO L290 TraceCheckUtils]: 1: Hoare triple {347#true} assume !(0 == ~cond); {347#true} is VALID [2022-04-07 12:29:27,717 INFO L290 TraceCheckUtils]: 2: Hoare triple {347#true} assume true; {347#true} is VALID [2022-04-07 12:29:27,718 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {347#true} {348#false} #85#return; {348#false} is VALID [2022-04-07 12:29:27,718 INFO L272 TraceCheckUtils]: 0: Hoare triple {347#true} call ULTIMATE.init(); {376#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-07 12:29:27,718 INFO L290 TraceCheckUtils]: 1: Hoare triple {376#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {347#true} is VALID [2022-04-07 12:29:27,718 INFO L290 TraceCheckUtils]: 2: Hoare triple {347#true} assume true; {347#true} is VALID [2022-04-07 12:29:27,719 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {347#true} {347#true} #91#return; {347#true} is VALID [2022-04-07 12:29:27,719 INFO L272 TraceCheckUtils]: 4: Hoare triple {347#true} call #t~ret19 := main(); {347#true} is VALID [2022-04-07 12:29:27,719 INFO L290 TraceCheckUtils]: 5: Hoare triple {347#true} assume -2147483648 <= #t~nondet14 && #t~nondet14 <= 2147483647;~n~0 := #t~nondet14;havoc #t~nondet14; {347#true} is VALID [2022-04-07 12:29:27,719 INFO L272 TraceCheckUtils]: 6: Hoare triple {347#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 < 1073741824 then 1 else 0)); {347#true} is VALID [2022-04-07 12:29:27,720 INFO L290 TraceCheckUtils]: 7: Hoare triple {347#true} ~cond := #in~cond; {347#true} is VALID [2022-04-07 12:29:27,720 INFO L290 TraceCheckUtils]: 8: Hoare triple {347#true} assume !(0 == ~cond); {347#true} is VALID [2022-04-07 12:29:27,720 INFO L290 TraceCheckUtils]: 9: Hoare triple {347#true} assume true; {347#true} is VALID [2022-04-07 12:29:27,723 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {347#true} {347#true} #75#return; {347#true} is VALID [2022-04-07 12:29:27,725 INFO L290 TraceCheckUtils]: 11: Hoare triple {347#true} call #t~malloc15.base, #t~malloc15.offset := #Ultimate.allocOnHeap(4 * ~n~0); {347#true} is VALID [2022-04-07 12:29:27,726 INFO L272 TraceCheckUtils]: 12: Hoare triple {347#true} call #Ultimate.meminit(#t~malloc15.base, #t~malloc15.offset, ~n~0, 4, 4 * ~n~0); {377#(= |#memory_int| |old(#memory_int)|)} is VALID [2022-04-07 12:29:27,728 INFO L290 TraceCheckUtils]: 13: Hoare triple {377#(= |#memory_int| |old(#memory_int)|)} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {378#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} is VALID [2022-04-07 12:29:27,728 INFO L290 TraceCheckUtils]: 14: Hoare triple {378#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} assume true; {378#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} is VALID [2022-04-07 12:29:27,729 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {378#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} {347#true} #77#return; {359#(= ((as const (Array Int Int)) 0) (select |#memory_int| |main_#t~malloc15.base|))} is VALID [2022-04-07 12:29:27,730 INFO L290 TraceCheckUtils]: 16: Hoare triple {359#(= ((as const (Array Int Int)) 0) (select |#memory_int| |main_#t~malloc15.base|))} ~a~0.base, ~a~0.offset := #t~malloc15.base, #t~malloc15.offset;assume -2147483648 <= #t~nondet16 && #t~nondet16 <= 2147483647;~x~0 := #t~nondet16;havoc #t~nondet16;assume -2147483648 <= #t~nondet17 && #t~nondet17 <= 2147483647;~y~0 := #t~nondet17;havoc #t~nondet17; {360#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} is VALID [2022-04-07 12:29:27,730 INFO L272 TraceCheckUtils]: 17: Hoare triple {360#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} call assume_abort_if_not((if ~x~0 >= 0 && ~y~0 >= 0 then 1 else 0)); {347#true} is VALID [2022-04-07 12:29:27,730 INFO L290 TraceCheckUtils]: 18: Hoare triple {347#true} ~cond := #in~cond; {347#true} is VALID [2022-04-07 12:29:27,730 INFO L290 TraceCheckUtils]: 19: Hoare triple {347#true} assume !(0 == ~cond); {347#true} is VALID [2022-04-07 12:29:27,731 INFO L290 TraceCheckUtils]: 20: Hoare triple {347#true} assume true; {347#true} is VALID [2022-04-07 12:29:27,731 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {347#true} {360#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} #79#return; {360#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} is VALID [2022-04-07 12:29:27,732 INFO L272 TraceCheckUtils]: 22: Hoare triple {360#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} call #t~ret18 := lcp(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0); {347#true} is VALID [2022-04-07 12:29:27,732 INFO L290 TraceCheckUtils]: 23: Hoare triple {347#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {379#(= |lcp_#in~a.base| lcp_~a.base)} is VALID [2022-04-07 12:29:27,733 INFO L290 TraceCheckUtils]: 24: Hoare triple {379#(= |lcp_#in~a.base| lcp_~a.base)} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {379#(= |lcp_#in~a.base| lcp_~a.base)} is VALID [2022-04-07 12:29:27,734 INFO L290 TraceCheckUtils]: 25: Hoare triple {379#(= |lcp_#in~a.base| lcp_~a.base)} assume #t~short7;call #t~mem5 := read~int(~a.base, ~a.offset + 4 * (~x + ~l~0), 4);call #t~mem6 := read~int(~a.base, ~a.offset + 4 * (~y + ~l~0), 4);#t~short7 := #t~mem5 == #t~mem6; {380#(or |lcp_#t~short7| (not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|))))} is VALID [2022-04-07 12:29:27,734 INFO L290 TraceCheckUtils]: 26: Hoare triple {380#(or |lcp_#t~short7| (not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|))))} assume !#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7; {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} is VALID [2022-04-07 12:29:27,735 INFO L290 TraceCheckUtils]: 27: Hoare triple {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} #res := ~l~0; {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} is VALID [2022-04-07 12:29:27,737 INFO L290 TraceCheckUtils]: 28: Hoare triple {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} assume true; {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} is VALID [2022-04-07 12:29:27,738 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {381#(not (= ((as const (Array Int Int)) 0) (select |#memory_int| |lcp_#in~a.base|)))} {360#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} #81#return; {348#false} is VALID [2022-04-07 12:29:27,745 INFO L290 TraceCheckUtils]: 30: Hoare triple {348#false} assume -2147483648 <= #t~ret18 && #t~ret18 <= 2147483647;~l~1 := #t~ret18;havoc #t~ret18; {348#false} is VALID [2022-04-07 12:29:27,745 INFO L272 TraceCheckUtils]: 31: Hoare triple {348#false} call check(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0, ~l~1); {348#false} is VALID [2022-04-07 12:29:27,746 INFO L290 TraceCheckUtils]: 32: Hoare triple {348#false} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l := #in~l;assume -2147483648 <= #t~nondet9 && #t~nondet9 <= 2147483647;~i~0 := #t~nondet9;havoc #t~nondet9; {348#false} is VALID [2022-04-07 12:29:27,746 INFO L272 TraceCheckUtils]: 33: Hoare triple {348#false} call assume_abort_if_not((if 0 <= ~i~0 && ~i~0 < ~l then 1 else 0)); {347#true} is VALID [2022-04-07 12:29:27,746 INFO L290 TraceCheckUtils]: 34: Hoare triple {347#true} ~cond := #in~cond; {347#true} is VALID [2022-04-07 12:29:27,746 INFO L290 TraceCheckUtils]: 35: Hoare triple {347#true} assume !(0 == ~cond); {347#true} is VALID [2022-04-07 12:29:27,746 INFO L290 TraceCheckUtils]: 36: Hoare triple {347#true} assume true; {347#true} is VALID [2022-04-07 12:29:27,746 INFO L284 TraceCheckUtils]: 37: Hoare quadruple {347#true} {348#false} #85#return; {348#false} is VALID [2022-04-07 12:29:27,746 INFO L290 TraceCheckUtils]: 38: Hoare triple {348#false} call #t~mem10 := read~int(~a.base, ~a.offset + 4 * (~x + ~i~0), 4);call #t~mem11 := read~int(~a.base, ~a.offset + 4 * (~y + ~i~0), 4); {348#false} is VALID [2022-04-07 12:29:27,746 INFO L272 TraceCheckUtils]: 39: Hoare triple {348#false} call __VERIFIER_assert((if #t~mem10 == #t~mem11 then 1 else 0)); {348#false} is VALID [2022-04-07 12:29:27,746 INFO L290 TraceCheckUtils]: 40: Hoare triple {348#false} ~cond := #in~cond; {348#false} is VALID [2022-04-07 12:29:27,747 INFO L290 TraceCheckUtils]: 41: Hoare triple {348#false} assume 0 == ~cond; {348#false} is VALID [2022-04-07 12:29:27,747 INFO L290 TraceCheckUtils]: 42: Hoare triple {348#false} assume !false; {348#false} is VALID [2022-04-07 12:29:27,747 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-07 12:29:27,747 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 12:29:27,747 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1561309318] [2022-04-07 12:29:27,748 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1561309318] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 12:29:27,748 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 12:29:27,748 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-07 12:29:27,748 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1748458754] [2022-04-07 12:29:27,748 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 12:29:27,749 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 3 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) Word has length 43 [2022-04-07 12:29:27,749 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 12:29:27,750 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 10 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 3 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 12:29:27,778 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 37 edges. 37 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 12:29:27,778 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-07 12:29:27,778 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 12:29:27,779 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-07 12:29:27,779 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2022-04-07 12:29:27,779 INFO L87 Difference]: Start difference. First operand 41 states and 45 transitions. Second operand has 10 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 3 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 12:29:28,464 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:28,465 INFO L93 Difference]: Finished difference Result 64 states and 69 transitions. [2022-04-07 12:29:28,465 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-07 12:29:28,465 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 3 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) Word has length 43 [2022-04-07 12:29:28,465 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 12:29:28,465 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 3 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 12:29:28,467 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 69 transitions. [2022-04-07 12:29:28,467 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 3 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 12:29:28,469 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 69 transitions. [2022-04-07 12:29:28,469 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 10 states and 69 transitions. [2022-04-07 12:29:28,535 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 69 edges. 69 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 12:29:28,537 INFO L225 Difference]: With dead ends: 64 [2022-04-07 12:29:28,537 INFO L226 Difference]: Without dead ends: 42 [2022-04-07 12:29:28,537 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=212, Unknown=0, NotChecked=0, Total=272 [2022-04-07 12:29:28,538 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 65 mSDsluCounter, 12 mSDsCounter, 0 mSdLazyCounter, 263 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 302 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 263 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-07 12:29:28,539 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [65 Valid, 43 Invalid, 302 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 263 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-07 12:29:28,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2022-04-07 12:29:28,544 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2022-04-07 12:29:28,544 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 12:29:28,544 INFO L82 GeneralOperation]: Start isEquivalent. First operand 42 states. Second operand has 42 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:28,544 INFO L74 IsIncluded]: Start isIncluded. First operand 42 states. Second operand has 42 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:28,545 INFO L87 Difference]: Start difference. First operand 42 states. Second operand has 42 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:28,547 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:28,547 INFO L93 Difference]: Finished difference Result 42 states and 46 transitions. [2022-04-07 12:29:28,547 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 46 transitions. [2022-04-07 12:29:28,547 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 12:29:28,548 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 12:29:28,548 INFO L74 IsIncluded]: Start isIncluded. First operand has 42 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 42 states. [2022-04-07 12:29:28,548 INFO L87 Difference]: Start difference. First operand has 42 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 42 states. [2022-04-07 12:29:28,550 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:28,550 INFO L93 Difference]: Finished difference Result 42 states and 46 transitions. [2022-04-07 12:29:28,550 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 46 transitions. [2022-04-07 12:29:28,551 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 12:29:28,551 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 12:29:28,551 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 12:29:28,551 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 12:29:28,551 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 10 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:28,553 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 46 transitions. [2022-04-07 12:29:28,553 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 46 transitions. Word has length 43 [2022-04-07 12:29:28,554 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 12:29:28,554 INFO L478 AbstractCegarLoop]: Abstraction has 42 states and 46 transitions. [2022-04-07 12:29:28,554 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 3 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 12:29:28,554 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 46 transitions. [2022-04-07 12:29:28,555 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-04-07 12:29:28,555 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 12:29:28,555 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 12:29:28,555 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-07 12:29:28,555 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 12:29:28,555 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 12:29:28,556 INFO L85 PathProgramCache]: Analyzing trace with hash -968487613, now seen corresponding path program 1 times [2022-04-07 12:29:28,556 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 12:29:28,556 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [126895334] [2022-04-07 12:29:28,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 12:29:28,556 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 12:29:28,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:28,660 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-07 12:29:28,661 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:28,672 INFO L290 TraceCheckUtils]: 0: Hoare triple {666#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {632#true} is VALID [2022-04-07 12:29:28,672 INFO L290 TraceCheckUtils]: 1: Hoare triple {632#true} assume true; {632#true} is VALID [2022-04-07 12:29:28,672 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {632#true} {632#true} #91#return; {632#true} is VALID [2022-04-07 12:29:28,672 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-07 12:29:28,673 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:28,680 INFO L290 TraceCheckUtils]: 0: Hoare triple {632#true} ~cond := #in~cond; {632#true} is VALID [2022-04-07 12:29:28,680 INFO L290 TraceCheckUtils]: 1: Hoare triple {632#true} assume !(0 == ~cond); {632#true} is VALID [2022-04-07 12:29:28,680 INFO L290 TraceCheckUtils]: 2: Hoare triple {632#true} assume true; {632#true} is VALID [2022-04-07 12:29:28,680 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {632#true} {632#true} #75#return; {632#true} is VALID [2022-04-07 12:29:28,687 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-07 12:29:28,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:28,706 INFO L290 TraceCheckUtils]: 0: Hoare triple {667#(= |#memory_int| |old(#memory_int)|)} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {668#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} is VALID [2022-04-07 12:29:28,706 INFO L290 TraceCheckUtils]: 1: Hoare triple {668#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} assume true; {668#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} is VALID [2022-04-07 12:29:28,707 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {668#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} {632#true} #77#return; {644#(= ((as const (Array Int Int)) 0) (select |#memory_int| |main_#t~malloc15.base|))} is VALID [2022-04-07 12:29:28,707 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-07 12:29:28,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:28,713 INFO L290 TraceCheckUtils]: 0: Hoare triple {632#true} ~cond := #in~cond; {632#true} is VALID [2022-04-07 12:29:28,713 INFO L290 TraceCheckUtils]: 1: Hoare triple {632#true} assume !(0 == ~cond); {632#true} is VALID [2022-04-07 12:29:28,713 INFO L290 TraceCheckUtils]: 2: Hoare triple {632#true} assume true; {632#true} is VALID [2022-04-07 12:29:28,714 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {632#true} {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} #79#return; {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} is VALID [2022-04-07 12:29:28,714 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-04-07 12:29:28,718 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:28,721 INFO L290 TraceCheckUtils]: 0: Hoare triple {632#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {632#true} is VALID [2022-04-07 12:29:28,722 INFO L290 TraceCheckUtils]: 1: Hoare triple {632#true} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {632#true} is VALID [2022-04-07 12:29:28,722 INFO L290 TraceCheckUtils]: 2: Hoare triple {632#true} assume !#t~short7; {632#true} is VALID [2022-04-07 12:29:28,722 INFO L290 TraceCheckUtils]: 3: Hoare triple {632#true} assume !#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7; {632#true} is VALID [2022-04-07 12:29:28,722 INFO L290 TraceCheckUtils]: 4: Hoare triple {632#true} #res := ~l~0; {632#true} is VALID [2022-04-07 12:29:28,722 INFO L290 TraceCheckUtils]: 5: Hoare triple {632#true} assume true; {632#true} is VALID [2022-04-07 12:29:28,723 INFO L284 TraceCheckUtils]: 6: Hoare quadruple {632#true} {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} #81#return; {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} is VALID [2022-04-07 12:29:28,723 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2022-04-07 12:29:28,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:28,727 INFO L290 TraceCheckUtils]: 0: Hoare triple {632#true} ~cond := #in~cond; {632#true} is VALID [2022-04-07 12:29:28,727 INFO L290 TraceCheckUtils]: 1: Hoare triple {632#true} assume !(0 == ~cond); {632#true} is VALID [2022-04-07 12:29:28,727 INFO L290 TraceCheckUtils]: 2: Hoare triple {632#true} assume true; {632#true} is VALID [2022-04-07 12:29:28,728 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {632#true} {658#(and (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~x) check_~a.offset)) 0) (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~y) check_~a.offset)) 0))} #85#return; {658#(and (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~x) check_~a.offset)) 0) (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~y) check_~a.offset)) 0))} is VALID [2022-04-07 12:29:28,728 INFO L272 TraceCheckUtils]: 0: Hoare triple {632#true} call ULTIMATE.init(); {666#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-07 12:29:28,728 INFO L290 TraceCheckUtils]: 1: Hoare triple {666#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {632#true} is VALID [2022-04-07 12:29:28,728 INFO L290 TraceCheckUtils]: 2: Hoare triple {632#true} assume true; {632#true} is VALID [2022-04-07 12:29:28,728 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {632#true} {632#true} #91#return; {632#true} is VALID [2022-04-07 12:29:28,728 INFO L272 TraceCheckUtils]: 4: Hoare triple {632#true} call #t~ret19 := main(); {632#true} is VALID [2022-04-07 12:29:28,729 INFO L290 TraceCheckUtils]: 5: Hoare triple {632#true} assume -2147483648 <= #t~nondet14 && #t~nondet14 <= 2147483647;~n~0 := #t~nondet14;havoc #t~nondet14; {632#true} is VALID [2022-04-07 12:29:28,729 INFO L272 TraceCheckUtils]: 6: Hoare triple {632#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 < 1073741824 then 1 else 0)); {632#true} is VALID [2022-04-07 12:29:28,729 INFO L290 TraceCheckUtils]: 7: Hoare triple {632#true} ~cond := #in~cond; {632#true} is VALID [2022-04-07 12:29:28,729 INFO L290 TraceCheckUtils]: 8: Hoare triple {632#true} assume !(0 == ~cond); {632#true} is VALID [2022-04-07 12:29:28,729 INFO L290 TraceCheckUtils]: 9: Hoare triple {632#true} assume true; {632#true} is VALID [2022-04-07 12:29:28,729 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {632#true} {632#true} #75#return; {632#true} is VALID [2022-04-07 12:29:28,729 INFO L290 TraceCheckUtils]: 11: Hoare triple {632#true} call #t~malloc15.base, #t~malloc15.offset := #Ultimate.allocOnHeap(4 * ~n~0); {632#true} is VALID [2022-04-07 12:29:28,730 INFO L272 TraceCheckUtils]: 12: Hoare triple {632#true} call #Ultimate.meminit(#t~malloc15.base, #t~malloc15.offset, ~n~0, 4, 4 * ~n~0); {667#(= |#memory_int| |old(#memory_int)|)} is VALID [2022-04-07 12:29:28,730 INFO L290 TraceCheckUtils]: 13: Hoare triple {667#(= |#memory_int| |old(#memory_int)|)} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {668#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} is VALID [2022-04-07 12:29:28,730 INFO L290 TraceCheckUtils]: 14: Hoare triple {668#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} assume true; {668#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} is VALID [2022-04-07 12:29:28,731 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {668#(= ((as const (Array Int Int)) 0) (select |#memory_int| |#Ultimate.meminit_#ptr.base|))} {632#true} #77#return; {644#(= ((as const (Array Int Int)) 0) (select |#memory_int| |main_#t~malloc15.base|))} is VALID [2022-04-07 12:29:28,732 INFO L290 TraceCheckUtils]: 16: Hoare triple {644#(= ((as const (Array Int Int)) 0) (select |#memory_int| |main_#t~malloc15.base|))} ~a~0.base, ~a~0.offset := #t~malloc15.base, #t~malloc15.offset;assume -2147483648 <= #t~nondet16 && #t~nondet16 <= 2147483647;~x~0 := #t~nondet16;havoc #t~nondet16;assume -2147483648 <= #t~nondet17 && #t~nondet17 <= 2147483647;~y~0 := #t~nondet17;havoc #t~nondet17; {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} is VALID [2022-04-07 12:29:28,732 INFO L272 TraceCheckUtils]: 17: Hoare triple {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} call assume_abort_if_not((if ~x~0 >= 0 && ~y~0 >= 0 then 1 else 0)); {632#true} is VALID [2022-04-07 12:29:28,732 INFO L290 TraceCheckUtils]: 18: Hoare triple {632#true} ~cond := #in~cond; {632#true} is VALID [2022-04-07 12:29:28,732 INFO L290 TraceCheckUtils]: 19: Hoare triple {632#true} assume !(0 == ~cond); {632#true} is VALID [2022-04-07 12:29:28,732 INFO L290 TraceCheckUtils]: 20: Hoare triple {632#true} assume true; {632#true} is VALID [2022-04-07 12:29:28,732 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {632#true} {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} #79#return; {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} is VALID [2022-04-07 12:29:28,732 INFO L272 TraceCheckUtils]: 22: Hoare triple {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} call #t~ret18 := lcp(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0); {632#true} is VALID [2022-04-07 12:29:28,733 INFO L290 TraceCheckUtils]: 23: Hoare triple {632#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {632#true} is VALID [2022-04-07 12:29:28,733 INFO L290 TraceCheckUtils]: 24: Hoare triple {632#true} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {632#true} is VALID [2022-04-07 12:29:28,733 INFO L290 TraceCheckUtils]: 25: Hoare triple {632#true} assume !#t~short7; {632#true} is VALID [2022-04-07 12:29:28,733 INFO L290 TraceCheckUtils]: 26: Hoare triple {632#true} assume !#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7; {632#true} is VALID [2022-04-07 12:29:28,733 INFO L290 TraceCheckUtils]: 27: Hoare triple {632#true} #res := ~l~0; {632#true} is VALID [2022-04-07 12:29:28,733 INFO L290 TraceCheckUtils]: 28: Hoare triple {632#true} assume true; {632#true} is VALID [2022-04-07 12:29:28,734 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {632#true} {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} #81#return; {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} is VALID [2022-04-07 12:29:28,734 INFO L290 TraceCheckUtils]: 30: Hoare triple {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} assume -2147483648 <= #t~ret18 && #t~ret18 <= 2147483647;~l~1 := #t~ret18;havoc #t~ret18; {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} is VALID [2022-04-07 12:29:28,735 INFO L272 TraceCheckUtils]: 31: Hoare triple {645#(= (select |#memory_int| main_~a~0.base) ((as const (Array Int Int)) 0))} call check(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0, ~l~1); {657#(= ((as const (Array Int Int)) 0) (select |#memory_int| |check_#in~a.base|))} is VALID [2022-04-07 12:29:28,735 INFO L290 TraceCheckUtils]: 32: Hoare triple {657#(= ((as const (Array Int Int)) 0) (select |#memory_int| |check_#in~a.base|))} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l := #in~l;assume -2147483648 <= #t~nondet9 && #t~nondet9 <= 2147483647;~i~0 := #t~nondet9;havoc #t~nondet9; {658#(and (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~x) check_~a.offset)) 0) (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~y) check_~a.offset)) 0))} is VALID [2022-04-07 12:29:28,736 INFO L272 TraceCheckUtils]: 33: Hoare triple {658#(and (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~x) check_~a.offset)) 0) (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~y) check_~a.offset)) 0))} call assume_abort_if_not((if 0 <= ~i~0 && ~i~0 < ~l then 1 else 0)); {632#true} is VALID [2022-04-07 12:29:28,736 INFO L290 TraceCheckUtils]: 34: Hoare triple {632#true} ~cond := #in~cond; {632#true} is VALID [2022-04-07 12:29:28,736 INFO L290 TraceCheckUtils]: 35: Hoare triple {632#true} assume !(0 == ~cond); {632#true} is VALID [2022-04-07 12:29:28,736 INFO L290 TraceCheckUtils]: 36: Hoare triple {632#true} assume true; {632#true} is VALID [2022-04-07 12:29:28,736 INFO L284 TraceCheckUtils]: 37: Hoare quadruple {632#true} {658#(and (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~x) check_~a.offset)) 0) (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~y) check_~a.offset)) 0))} #85#return; {658#(and (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~x) check_~a.offset)) 0) (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~y) check_~a.offset)) 0))} is VALID [2022-04-07 12:29:28,737 INFO L290 TraceCheckUtils]: 38: Hoare triple {658#(and (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~x) check_~a.offset)) 0) (= (select (select |#memory_int| check_~a.base) (+ (* check_~i~0 4) (* 4 check_~y) check_~a.offset)) 0))} call #t~mem10 := read~int(~a.base, ~a.offset + 4 * (~x + ~i~0), 4);call #t~mem11 := read~int(~a.base, ~a.offset + 4 * (~y + ~i~0), 4); {663#(= |check_#t~mem11| |check_#t~mem10|)} is VALID [2022-04-07 12:29:28,737 INFO L272 TraceCheckUtils]: 39: Hoare triple {663#(= |check_#t~mem11| |check_#t~mem10|)} call __VERIFIER_assert((if #t~mem10 == #t~mem11 then 1 else 0)); {664#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-07 12:29:28,738 INFO L290 TraceCheckUtils]: 40: Hoare triple {664#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {665#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-07 12:29:28,738 INFO L290 TraceCheckUtils]: 41: Hoare triple {665#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {633#false} is VALID [2022-04-07 12:29:28,738 INFO L290 TraceCheckUtils]: 42: Hoare triple {633#false} assume !false; {633#false} is VALID [2022-04-07 12:29:28,738 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-07 12:29:28,738 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 12:29:28,738 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [126895334] [2022-04-07 12:29:28,738 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [126895334] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 12:29:28,738 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 12:29:28,739 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-07 12:29:28,739 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1347283515] [2022-04-07 12:29:28,739 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 12:29:28,739 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.0) internal successors, (22), 7 states have internal predecessors, (22), 4 states have call successors, (9), 5 states have call predecessors, (9), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) Word has length 43 [2022-04-07 12:29:28,739 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 12:29:28,740 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 12 states, 11 states have (on average 2.0) internal successors, (22), 7 states have internal predecessors, (22), 4 states have call successors, (9), 5 states have call predecessors, (9), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 12:29:28,764 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 37 edges. 37 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 12:29:28,764 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-07 12:29:28,764 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 12:29:28,764 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-07 12:29:28,764 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2022-04-07 12:29:28,765 INFO L87 Difference]: Start difference. First operand 42 states and 46 transitions. Second operand has 12 states, 11 states have (on average 2.0) internal successors, (22), 7 states have internal predecessors, (22), 4 states have call successors, (9), 5 states have call predecessors, (9), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 12:29:29,567 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:29,568 INFO L93 Difference]: Finished difference Result 48 states and 51 transitions. [2022-04-07 12:29:29,568 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-07 12:29:29,568 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.0) internal successors, (22), 7 states have internal predecessors, (22), 4 states have call successors, (9), 5 states have call predecessors, (9), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) Word has length 43 [2022-04-07 12:29:29,568 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 12:29:29,568 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 11 states have (on average 2.0) internal successors, (22), 7 states have internal predecessors, (22), 4 states have call successors, (9), 5 states have call predecessors, (9), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 12:29:29,570 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 50 transitions. [2022-04-07 12:29:29,570 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 11 states have (on average 2.0) internal successors, (22), 7 states have internal predecessors, (22), 4 states have call successors, (9), 5 states have call predecessors, (9), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 12:29:29,571 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 50 transitions. [2022-04-07 12:29:29,571 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 13 states and 50 transitions. [2022-04-07 12:29:29,618 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 50 edges. 50 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 12:29:29,619 INFO L225 Difference]: With dead ends: 48 [2022-04-07 12:29:29,619 INFO L226 Difference]: Without dead ends: 44 [2022-04-07 12:29:29,620 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=84, Invalid=378, Unknown=0, NotChecked=0, Total=462 [2022-04-07 12:29:29,620 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 69 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 341 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 46 SdHoareTripleChecker+Invalid, 377 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 341 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-07 12:29:29,621 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [69 Valid, 46 Invalid, 377 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 341 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-07 12:29:29,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-07 12:29:29,625 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2022-04-07 12:29:29,625 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 12:29:29,625 INFO L82 GeneralOperation]: Start isEquivalent. First operand 44 states. Second operand has 44 states, 28 states have (on average 1.0714285714285714) internal successors, (30), 28 states have internal predecessors, (30), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:29,625 INFO L74 IsIncluded]: Start isIncluded. First operand 44 states. Second operand has 44 states, 28 states have (on average 1.0714285714285714) internal successors, (30), 28 states have internal predecessors, (30), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:29,626 INFO L87 Difference]: Start difference. First operand 44 states. Second operand has 44 states, 28 states have (on average 1.0714285714285714) internal successors, (30), 28 states have internal predecessors, (30), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:29,628 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:29,628 INFO L93 Difference]: Finished difference Result 44 states and 47 transitions. [2022-04-07 12:29:29,628 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 47 transitions. [2022-04-07 12:29:29,628 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 12:29:29,628 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 12:29:29,629 INFO L74 IsIncluded]: Start isIncluded. First operand has 44 states, 28 states have (on average 1.0714285714285714) internal successors, (30), 28 states have internal predecessors, (30), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 44 states. [2022-04-07 12:29:29,629 INFO L87 Difference]: Start difference. First operand has 44 states, 28 states have (on average 1.0714285714285714) internal successors, (30), 28 states have internal predecessors, (30), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 44 states. [2022-04-07 12:29:29,630 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:29,630 INFO L93 Difference]: Finished difference Result 44 states and 47 transitions. [2022-04-07 12:29:29,630 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 47 transitions. [2022-04-07 12:29:29,630 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 12:29:29,631 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 12:29:29,631 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 12:29:29,631 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 12:29:29,631 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 28 states have (on average 1.0714285714285714) internal successors, (30), 28 states have internal predecessors, (30), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:29,632 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 47 transitions. [2022-04-07 12:29:29,632 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 47 transitions. Word has length 43 [2022-04-07 12:29:29,632 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 12:29:29,632 INFO L478 AbstractCegarLoop]: Abstraction has 44 states and 47 transitions. [2022-04-07 12:29:29,632 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.0) internal successors, (22), 7 states have internal predecessors, (22), 4 states have call successors, (9), 5 states have call predecessors, (9), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 12:29:29,632 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 47 transitions. [2022-04-07 12:29:29,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-07 12:29:29,633 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 12:29:29,633 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 12:29:29,633 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-07 12:29:29,633 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 12:29:29,634 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 12:29:29,634 INFO L85 PathProgramCache]: Analyzing trace with hash -582845443, now seen corresponding path program 1 times [2022-04-07 12:29:29,634 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 12:29:29,634 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [204942595] [2022-04-07 12:29:29,634 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 12:29:29,634 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 12:29:29,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:29,747 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-07 12:29:29,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:29,752 INFO L290 TraceCheckUtils]: 0: Hoare triple {945#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {910#true} is VALID [2022-04-07 12:29:29,752 INFO L290 TraceCheckUtils]: 1: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,752 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {910#true} {910#true} #91#return; {910#true} is VALID [2022-04-07 12:29:29,752 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-07 12:29:29,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:29,754 INFO L290 TraceCheckUtils]: 0: Hoare triple {910#true} ~cond := #in~cond; {910#true} is VALID [2022-04-07 12:29:29,754 INFO L290 TraceCheckUtils]: 1: Hoare triple {910#true} assume !(0 == ~cond); {910#true} is VALID [2022-04-07 12:29:29,754 INFO L290 TraceCheckUtils]: 2: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,755 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {910#true} {910#true} #75#return; {910#true} is VALID [2022-04-07 12:29:29,759 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-07 12:29:29,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:29,762 INFO L290 TraceCheckUtils]: 0: Hoare triple {946#(= |#memory_int| |old(#memory_int)|)} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {910#true} is VALID [2022-04-07 12:29:29,762 INFO L290 TraceCheckUtils]: 1: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,762 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {910#true} {910#true} #77#return; {910#true} is VALID [2022-04-07 12:29:29,762 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-07 12:29:29,763 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:29,764 INFO L290 TraceCheckUtils]: 0: Hoare triple {910#true} ~cond := #in~cond; {910#true} is VALID [2022-04-07 12:29:29,764 INFO L290 TraceCheckUtils]: 1: Hoare triple {910#true} assume !(0 == ~cond); {910#true} is VALID [2022-04-07 12:29:29,765 INFO L290 TraceCheckUtils]: 2: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,765 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {910#true} {910#true} #79#return; {910#true} is VALID [2022-04-07 12:29:29,765 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-04-07 12:29:29,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:29,882 INFO L290 TraceCheckUtils]: 0: Hoare triple {910#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {947#(and (<= lcp_~l~0 0) (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n) (<= 0 lcp_~l~0))} is VALID [2022-04-07 12:29:29,883 INFO L290 TraceCheckUtils]: 1: Hoare triple {947#(and (<= lcp_~l~0 0) (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n) (<= 0 lcp_~l~0))} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {948#(and (<= lcp_~l~0 0) (<= 0 lcp_~l~0) (or |lcp_#t~short7| (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)))} is VALID [2022-04-07 12:29:29,883 INFO L290 TraceCheckUtils]: 2: Hoare triple {948#(and (<= lcp_~l~0 0) (<= 0 lcp_~l~0) (or |lcp_#t~short7| (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)))} assume !#t~short7; {949#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= lcp_~l~0 0) (<= 0 lcp_~l~0))} is VALID [2022-04-07 12:29:29,884 INFO L290 TraceCheckUtils]: 3: Hoare triple {949#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= lcp_~l~0 0) (<= 0 lcp_~l~0))} assume !#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7; {949#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= lcp_~l~0 0) (<= 0 lcp_~l~0))} is VALID [2022-04-07 12:29:29,884 INFO L290 TraceCheckUtils]: 4: Hoare triple {949#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= lcp_~l~0 0) (<= 0 lcp_~l~0))} #res := ~l~0; {950#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= |lcp_#res| 0) (<= 0 |lcp_#res|))} is VALID [2022-04-07 12:29:29,884 INFO L290 TraceCheckUtils]: 5: Hoare triple {950#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= |lcp_#res| 0) (<= 0 |lcp_#res|))} assume true; {950#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= |lcp_#res| 0) (<= 0 |lcp_#res|))} is VALID [2022-04-07 12:29:29,885 INFO L284 TraceCheckUtils]: 6: Hoare quadruple {950#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= |lcp_#res| 0) (<= 0 |lcp_#res|))} {910#true} #81#return; {933#(and (= |main_#t~ret18| 0) (or (<= main_~n~0 main_~x~0) (<= main_~n~0 main_~y~0)))} is VALID [2022-04-07 12:29:29,886 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2022-04-07 12:29:29,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:29,900 INFO L290 TraceCheckUtils]: 0: Hoare triple {910#true} ~cond := #in~cond; {910#true} is VALID [2022-04-07 12:29:29,900 INFO L290 TraceCheckUtils]: 1: Hoare triple {910#true} assume !(0 == ~cond); {910#true} is VALID [2022-04-07 12:29:29,900 INFO L290 TraceCheckUtils]: 2: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,901 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {910#true} {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} #85#return; {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} is VALID [2022-04-07 12:29:29,901 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2022-04-07 12:29:29,903 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:29,908 INFO L290 TraceCheckUtils]: 0: Hoare triple {910#true} ~cond := #in~cond; {910#true} is VALID [2022-04-07 12:29:29,908 INFO L290 TraceCheckUtils]: 1: Hoare triple {910#true} assume !(0 == ~cond); {910#true} is VALID [2022-04-07 12:29:29,908 INFO L290 TraceCheckUtils]: 2: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,909 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {910#true} {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} #87#return; {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} is VALID [2022-04-07 12:29:29,909 INFO L272 TraceCheckUtils]: 0: Hoare triple {910#true} call ULTIMATE.init(); {945#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-07 12:29:29,909 INFO L290 TraceCheckUtils]: 1: Hoare triple {945#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {910#true} is VALID [2022-04-07 12:29:29,909 INFO L290 TraceCheckUtils]: 2: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,910 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {910#true} {910#true} #91#return; {910#true} is VALID [2022-04-07 12:29:29,910 INFO L272 TraceCheckUtils]: 4: Hoare triple {910#true} call #t~ret19 := main(); {910#true} is VALID [2022-04-07 12:29:29,910 INFO L290 TraceCheckUtils]: 5: Hoare triple {910#true} assume -2147483648 <= #t~nondet14 && #t~nondet14 <= 2147483647;~n~0 := #t~nondet14;havoc #t~nondet14; {910#true} is VALID [2022-04-07 12:29:29,910 INFO L272 TraceCheckUtils]: 6: Hoare triple {910#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 < 1073741824 then 1 else 0)); {910#true} is VALID [2022-04-07 12:29:29,910 INFO L290 TraceCheckUtils]: 7: Hoare triple {910#true} ~cond := #in~cond; {910#true} is VALID [2022-04-07 12:29:29,910 INFO L290 TraceCheckUtils]: 8: Hoare triple {910#true} assume !(0 == ~cond); {910#true} is VALID [2022-04-07 12:29:29,910 INFO L290 TraceCheckUtils]: 9: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,910 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {910#true} {910#true} #75#return; {910#true} is VALID [2022-04-07 12:29:29,910 INFO L290 TraceCheckUtils]: 11: Hoare triple {910#true} call #t~malloc15.base, #t~malloc15.offset := #Ultimate.allocOnHeap(4 * ~n~0); {910#true} is VALID [2022-04-07 12:29:29,911 INFO L272 TraceCheckUtils]: 12: Hoare triple {910#true} call #Ultimate.meminit(#t~malloc15.base, #t~malloc15.offset, ~n~0, 4, 4 * ~n~0); {946#(= |#memory_int| |old(#memory_int)|)} is VALID [2022-04-07 12:29:29,915 INFO L290 TraceCheckUtils]: 13: Hoare triple {946#(= |#memory_int| |old(#memory_int)|)} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {910#true} is VALID [2022-04-07 12:29:29,915 INFO L290 TraceCheckUtils]: 14: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,916 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {910#true} {910#true} #77#return; {910#true} is VALID [2022-04-07 12:29:29,916 INFO L290 TraceCheckUtils]: 16: Hoare triple {910#true} ~a~0.base, ~a~0.offset := #t~malloc15.base, #t~malloc15.offset;assume -2147483648 <= #t~nondet16 && #t~nondet16 <= 2147483647;~x~0 := #t~nondet16;havoc #t~nondet16;assume -2147483648 <= #t~nondet17 && #t~nondet17 <= 2147483647;~y~0 := #t~nondet17;havoc #t~nondet17; {910#true} is VALID [2022-04-07 12:29:29,920 INFO L272 TraceCheckUtils]: 17: Hoare triple {910#true} call assume_abort_if_not((if ~x~0 >= 0 && ~y~0 >= 0 then 1 else 0)); {910#true} is VALID [2022-04-07 12:29:29,920 INFO L290 TraceCheckUtils]: 18: Hoare triple {910#true} ~cond := #in~cond; {910#true} is VALID [2022-04-07 12:29:29,921 INFO L290 TraceCheckUtils]: 19: Hoare triple {910#true} assume !(0 == ~cond); {910#true} is VALID [2022-04-07 12:29:29,921 INFO L290 TraceCheckUtils]: 20: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,921 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {910#true} {910#true} #79#return; {910#true} is VALID [2022-04-07 12:29:29,921 INFO L272 TraceCheckUtils]: 22: Hoare triple {910#true} call #t~ret18 := lcp(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0); {910#true} is VALID [2022-04-07 12:29:29,922 INFO L290 TraceCheckUtils]: 23: Hoare triple {910#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {947#(and (<= lcp_~l~0 0) (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n) (<= 0 lcp_~l~0))} is VALID [2022-04-07 12:29:29,923 INFO L290 TraceCheckUtils]: 24: Hoare triple {947#(and (<= lcp_~l~0 0) (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n) (<= 0 lcp_~l~0))} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {948#(and (<= lcp_~l~0 0) (<= 0 lcp_~l~0) (or |lcp_#t~short7| (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)))} is VALID [2022-04-07 12:29:29,924 INFO L290 TraceCheckUtils]: 25: Hoare triple {948#(and (<= lcp_~l~0 0) (<= 0 lcp_~l~0) (or |lcp_#t~short7| (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)))} assume !#t~short7; {949#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= lcp_~l~0 0) (<= 0 lcp_~l~0))} is VALID [2022-04-07 12:29:29,927 INFO L290 TraceCheckUtils]: 26: Hoare triple {949#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= lcp_~l~0 0) (<= 0 lcp_~l~0))} assume !#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7; {949#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= lcp_~l~0 0) (<= 0 lcp_~l~0))} is VALID [2022-04-07 12:29:29,927 INFO L290 TraceCheckUtils]: 27: Hoare triple {949#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= lcp_~l~0 0) (<= 0 lcp_~l~0))} #res := ~l~0; {950#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= |lcp_#res| 0) (<= 0 |lcp_#res|))} is VALID [2022-04-07 12:29:29,928 INFO L290 TraceCheckUtils]: 28: Hoare triple {950#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= |lcp_#res| 0) (<= 0 |lcp_#res|))} assume true; {950#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= |lcp_#res| 0) (<= 0 |lcp_#res|))} is VALID [2022-04-07 12:29:29,929 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {950#(and (or (<= |lcp_#in~n| |lcp_#in~x|) (<= |lcp_#in~n| |lcp_#in~y|)) (<= |lcp_#res| 0) (<= 0 |lcp_#res|))} {910#true} #81#return; {933#(and (= |main_#t~ret18| 0) (or (<= main_~n~0 main_~x~0) (<= main_~n~0 main_~y~0)))} is VALID [2022-04-07 12:29:29,929 INFO L290 TraceCheckUtils]: 30: Hoare triple {933#(and (= |main_#t~ret18| 0) (or (<= main_~n~0 main_~x~0) (<= main_~n~0 main_~y~0)))} assume -2147483648 <= #t~ret18 && #t~ret18 <= 2147483647;~l~1 := #t~ret18;havoc #t~ret18; {934#(and (= main_~l~1 0) (or (<= main_~n~0 main_~x~0) (<= main_~n~0 main_~y~0)))} is VALID [2022-04-07 12:29:29,930 INFO L272 TraceCheckUtils]: 31: Hoare triple {934#(and (= main_~l~1 0) (or (<= main_~n~0 main_~x~0) (<= main_~n~0 main_~y~0)))} call check(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0, ~l~1); {935#(and (= |check_#in~l| 0) (or (<= |check_#in~n| |check_#in~x|) (<= |check_#in~n| |check_#in~y|)))} is VALID [2022-04-07 12:29:29,930 INFO L290 TraceCheckUtils]: 32: Hoare triple {935#(and (= |check_#in~l| 0) (or (<= |check_#in~n| |check_#in~x|) (<= |check_#in~n| |check_#in~y|)))} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l := #in~l;assume -2147483648 <= #t~nondet9 && #t~nondet9 <= 2147483647;~i~0 := #t~nondet9;havoc #t~nondet9; {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} is VALID [2022-04-07 12:29:29,931 INFO L272 TraceCheckUtils]: 33: Hoare triple {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} call assume_abort_if_not((if 0 <= ~i~0 && ~i~0 < ~l then 1 else 0)); {910#true} is VALID [2022-04-07 12:29:29,931 INFO L290 TraceCheckUtils]: 34: Hoare triple {910#true} ~cond := #in~cond; {910#true} is VALID [2022-04-07 12:29:29,931 INFO L290 TraceCheckUtils]: 35: Hoare triple {910#true} assume !(0 == ~cond); {910#true} is VALID [2022-04-07 12:29:29,931 INFO L290 TraceCheckUtils]: 36: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,931 INFO L284 TraceCheckUtils]: 37: Hoare quadruple {910#true} {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} #85#return; {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} is VALID [2022-04-07 12:29:29,932 INFO L290 TraceCheckUtils]: 38: Hoare triple {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} call #t~mem10 := read~int(~a.base, ~a.offset + 4 * (~x + ~i~0), 4);call #t~mem11 := read~int(~a.base, ~a.offset + 4 * (~y + ~i~0), 4); {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} is VALID [2022-04-07 12:29:29,932 INFO L272 TraceCheckUtils]: 39: Hoare triple {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} call __VERIFIER_assert((if #t~mem10 == #t~mem11 then 1 else 0)); {910#true} is VALID [2022-04-07 12:29:29,932 INFO L290 TraceCheckUtils]: 40: Hoare triple {910#true} ~cond := #in~cond; {910#true} is VALID [2022-04-07 12:29:29,932 INFO L290 TraceCheckUtils]: 41: Hoare triple {910#true} assume !(0 == ~cond); {910#true} is VALID [2022-04-07 12:29:29,932 INFO L290 TraceCheckUtils]: 42: Hoare triple {910#true} assume true; {910#true} is VALID [2022-04-07 12:29:29,932 INFO L284 TraceCheckUtils]: 43: Hoare quadruple {910#true} {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} #87#return; {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} is VALID [2022-04-07 12:29:29,933 INFO L290 TraceCheckUtils]: 44: Hoare triple {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} havoc #t~mem10;havoc #t~mem11; {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} is VALID [2022-04-07 12:29:29,933 INFO L290 TraceCheckUtils]: 45: Hoare triple {936#(and (= check_~l 0) (or (<= check_~n check_~y) (<= check_~n check_~x)))} assume ~x + ~l < ~n && ~y + ~l < ~n;call #t~mem12 := read~int(~a.base, ~a.offset + 4 * (~x + ~l), 4);call #t~mem13 := read~int(~a.base, ~a.offset + 4 * (~y + ~l), 4); {911#false} is VALID [2022-04-07 12:29:29,933 INFO L272 TraceCheckUtils]: 46: Hoare triple {911#false} call __VERIFIER_assert((if #t~mem12 != #t~mem13 then 1 else 0)); {911#false} is VALID [2022-04-07 12:29:29,933 INFO L290 TraceCheckUtils]: 47: Hoare triple {911#false} ~cond := #in~cond; {911#false} is VALID [2022-04-07 12:29:29,934 INFO L290 TraceCheckUtils]: 48: Hoare triple {911#false} assume 0 == ~cond; {911#false} is VALID [2022-04-07 12:29:29,934 INFO L290 TraceCheckUtils]: 49: Hoare triple {911#false} assume !false; {911#false} is VALID [2022-04-07 12:29:29,934 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-07 12:29:29,934 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 12:29:29,934 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [204942595] [2022-04-07 12:29:29,934 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [204942595] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 12:29:29,934 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 12:29:29,934 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-07 12:29:29,934 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1432422529] [2022-04-07 12:29:29,934 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 12:29:29,935 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 8 states have internal predecessors, (27), 4 states have call successors, (10), 5 states have call predecessors, (10), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 50 [2022-04-07 12:29:29,935 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 12:29:29,935 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 8 states have internal predecessors, (27), 4 states have call successors, (10), 5 states have call predecessors, (10), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-07 12:29:29,964 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 12:29:29,964 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-07 12:29:29,964 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 12:29:29,964 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-07 12:29:29,964 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=110, Unknown=0, NotChecked=0, Total=132 [2022-04-07 12:29:29,964 INFO L87 Difference]: Start difference. First operand 44 states and 47 transitions. Second operand has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 8 states have internal predecessors, (27), 4 states have call successors, (10), 5 states have call predecessors, (10), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-07 12:29:31,002 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:31,002 INFO L93 Difference]: Finished difference Result 64 states and 70 transitions. [2022-04-07 12:29:31,002 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-07 12:29:31,003 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 8 states have internal predecessors, (27), 4 states have call successors, (10), 5 states have call predecessors, (10), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 50 [2022-04-07 12:29:31,003 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 12:29:31,004 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 8 states have internal predecessors, (27), 4 states have call successors, (10), 5 states have call predecessors, (10), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-07 12:29:31,007 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 68 transitions. [2022-04-07 12:29:31,007 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 8 states have internal predecessors, (27), 4 states have call successors, (10), 5 states have call predecessors, (10), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-07 12:29:31,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 68 transitions. [2022-04-07 12:29:31,009 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 13 states and 68 transitions. [2022-04-07 12:29:31,074 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 68 edges. 68 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 12:29:31,075 INFO L225 Difference]: With dead ends: 64 [2022-04-07 12:29:31,075 INFO L226 Difference]: Without dead ends: 48 [2022-04-07 12:29:31,075 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=84, Invalid=336, Unknown=0, NotChecked=0, Total=420 [2022-04-07 12:29:31,076 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 72 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 415 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 46 SdHoareTripleChecker+Invalid, 458 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 415 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-04-07 12:29:31,076 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [75 Valid, 46 Invalid, 458 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 415 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-04-07 12:29:31,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-07 12:29:31,082 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 46. [2022-04-07 12:29:31,082 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 12:29:31,082 INFO L82 GeneralOperation]: Start isEquivalent. First operand 48 states. Second operand has 46 states, 30 states have (on average 1.1) internal successors, (33), 30 states have internal predecessors, (33), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:31,082 INFO L74 IsIncluded]: Start isIncluded. First operand 48 states. Second operand has 46 states, 30 states have (on average 1.1) internal successors, (33), 30 states have internal predecessors, (33), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:31,082 INFO L87 Difference]: Start difference. First operand 48 states. Second operand has 46 states, 30 states have (on average 1.1) internal successors, (33), 30 states have internal predecessors, (33), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:31,083 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:31,084 INFO L93 Difference]: Finished difference Result 48 states and 52 transitions. [2022-04-07 12:29:31,084 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 52 transitions. [2022-04-07 12:29:31,084 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 12:29:31,084 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 12:29:31,084 INFO L74 IsIncluded]: Start isIncluded. First operand has 46 states, 30 states have (on average 1.1) internal successors, (33), 30 states have internal predecessors, (33), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 48 states. [2022-04-07 12:29:31,084 INFO L87 Difference]: Start difference. First operand has 46 states, 30 states have (on average 1.1) internal successors, (33), 30 states have internal predecessors, (33), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 48 states. [2022-04-07 12:29:31,085 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:31,086 INFO L93 Difference]: Finished difference Result 48 states and 52 transitions. [2022-04-07 12:29:31,086 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 52 transitions. [2022-04-07 12:29:31,086 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 12:29:31,086 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 12:29:31,086 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 12:29:31,086 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 12:29:31,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 30 states have (on average 1.1) internal successors, (33), 30 states have internal predecessors, (33), 10 states have call successors, (10), 8 states have call predecessors, (10), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 12:29:31,089 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 50 transitions. [2022-04-07 12:29:31,089 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 50 transitions. Word has length 50 [2022-04-07 12:29:31,089 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 12:29:31,089 INFO L478 AbstractCegarLoop]: Abstraction has 46 states and 50 transitions. [2022-04-07 12:29:31,089 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 8 states have internal predecessors, (27), 4 states have call successors, (10), 5 states have call predecessors, (10), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-07 12:29:31,089 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 50 transitions. [2022-04-07 12:29:31,090 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2022-04-07 12:29:31,090 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 12:29:31,090 INFO L499 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 12:29:31,090 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-04-07 12:29:31,090 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 12:29:31,090 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 12:29:31,090 INFO L85 PathProgramCache]: Analyzing trace with hash 611931899, now seen corresponding path program 1 times [2022-04-07 12:29:31,091 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 12:29:31,091 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [415371337] [2022-04-07 12:29:31,091 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 12:29:31,091 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 12:29:31,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:31,186 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-07 12:29:31,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:31,190 INFO L290 TraceCheckUtils]: 0: Hoare triple {1262#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {1224#true} is VALID [2022-04-07 12:29:31,190 INFO L290 TraceCheckUtils]: 1: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,191 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {1224#true} {1224#true} #91#return; {1224#true} is VALID [2022-04-07 12:29:31,191 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-07 12:29:31,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:31,193 INFO L290 TraceCheckUtils]: 0: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:31,193 INFO L290 TraceCheckUtils]: 1: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:31,193 INFO L290 TraceCheckUtils]: 2: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,193 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1224#true} {1224#true} #75#return; {1224#true} is VALID [2022-04-07 12:29:31,198 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-07 12:29:31,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:31,202 INFO L290 TraceCheckUtils]: 0: Hoare triple {1263#(= |#memory_int| |old(#memory_int)|)} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {1224#true} is VALID [2022-04-07 12:29:31,202 INFO L290 TraceCheckUtils]: 1: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,202 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {1224#true} {1224#true} #77#return; {1224#true} is VALID [2022-04-07 12:29:31,202 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-07 12:29:31,203 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:31,205 INFO L290 TraceCheckUtils]: 0: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:31,205 INFO L290 TraceCheckUtils]: 1: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:31,205 INFO L290 TraceCheckUtils]: 2: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,205 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1224#true} {1224#true} #79#return; {1224#true} is VALID [2022-04-07 12:29:31,205 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-04-07 12:29:31,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:31,297 INFO L290 TraceCheckUtils]: 0: Hoare triple {1224#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} is VALID [2022-04-07 12:29:31,298 INFO L290 TraceCheckUtils]: 1: Hoare triple {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} is VALID [2022-04-07 12:29:31,298 INFO L290 TraceCheckUtils]: 2: Hoare triple {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} assume #t~short7;call #t~mem5 := read~int(~a.base, ~a.offset + 4 * (~x + ~l~0), 4);call #t~mem6 := read~int(~a.base, ~a.offset + 4 * (~y + ~l~0), 4);#t~short7 := #t~mem5 == #t~mem6; {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} is VALID [2022-04-07 12:29:31,299 INFO L290 TraceCheckUtils]: 3: Hoare triple {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} assume !!#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7;#t~post8 := ~l~0;~l~0 := 1 + #t~post8;havoc #t~post8; {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} is VALID [2022-04-07 12:29:31,299 INFO L290 TraceCheckUtils]: 4: Hoare triple {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {1265#(or |lcp_#t~short7| (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:31,299 INFO L290 TraceCheckUtils]: 5: Hoare triple {1265#(or |lcp_#t~short7| (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} assume !#t~short7; {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:31,300 INFO L290 TraceCheckUtils]: 6: Hoare triple {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} assume !#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7; {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:31,300 INFO L290 TraceCheckUtils]: 7: Hoare triple {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} #res := ~l~0; {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} is VALID [2022-04-07 12:29:31,300 INFO L290 TraceCheckUtils]: 8: Hoare triple {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} assume true; {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} is VALID [2022-04-07 12:29:31,301 INFO L284 TraceCheckUtils]: 9: Hoare quadruple {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} {1224#true} #81#return; {1250#(or (<= main_~n~0 (+ |main_#t~ret18| main_~x~0)) (<= main_~n~0 (+ |main_#t~ret18| main_~y~0)))} is VALID [2022-04-07 12:29:31,301 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2022-04-07 12:29:31,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:31,307 INFO L290 TraceCheckUtils]: 0: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:31,307 INFO L290 TraceCheckUtils]: 1: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:31,307 INFO L290 TraceCheckUtils]: 2: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,308 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1224#true} {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} #85#return; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:31,308 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2022-04-07 12:29:31,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:31,312 INFO L290 TraceCheckUtils]: 0: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:31,312 INFO L290 TraceCheckUtils]: 1: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:31,312 INFO L290 TraceCheckUtils]: 2: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,313 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1224#true} {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} #87#return; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:31,313 INFO L272 TraceCheckUtils]: 0: Hoare triple {1224#true} call ULTIMATE.init(); {1262#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-07 12:29:31,313 INFO L290 TraceCheckUtils]: 1: Hoare triple {1262#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {1224#true} is VALID [2022-04-07 12:29:31,313 INFO L290 TraceCheckUtils]: 2: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,313 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1224#true} {1224#true} #91#return; {1224#true} is VALID [2022-04-07 12:29:31,313 INFO L272 TraceCheckUtils]: 4: Hoare triple {1224#true} call #t~ret19 := main(); {1224#true} is VALID [2022-04-07 12:29:31,313 INFO L290 TraceCheckUtils]: 5: Hoare triple {1224#true} assume -2147483648 <= #t~nondet14 && #t~nondet14 <= 2147483647;~n~0 := #t~nondet14;havoc #t~nondet14; {1224#true} is VALID [2022-04-07 12:29:31,314 INFO L272 TraceCheckUtils]: 6: Hoare triple {1224#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 < 1073741824 then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:31,314 INFO L290 TraceCheckUtils]: 7: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:31,314 INFO L290 TraceCheckUtils]: 8: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:31,314 INFO L290 TraceCheckUtils]: 9: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,314 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1224#true} {1224#true} #75#return; {1224#true} is VALID [2022-04-07 12:29:31,314 INFO L290 TraceCheckUtils]: 11: Hoare triple {1224#true} call #t~malloc15.base, #t~malloc15.offset := #Ultimate.allocOnHeap(4 * ~n~0); {1224#true} is VALID [2022-04-07 12:29:31,314 INFO L272 TraceCheckUtils]: 12: Hoare triple {1224#true} call #Ultimate.meminit(#t~malloc15.base, #t~malloc15.offset, ~n~0, 4, 4 * ~n~0); {1263#(= |#memory_int| |old(#memory_int)|)} is VALID [2022-04-07 12:29:31,314 INFO L290 TraceCheckUtils]: 13: Hoare triple {1263#(= |#memory_int| |old(#memory_int)|)} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {1224#true} is VALID [2022-04-07 12:29:31,315 INFO L290 TraceCheckUtils]: 14: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,315 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1224#true} {1224#true} #77#return; {1224#true} is VALID [2022-04-07 12:29:31,315 INFO L290 TraceCheckUtils]: 16: Hoare triple {1224#true} ~a~0.base, ~a~0.offset := #t~malloc15.base, #t~malloc15.offset;assume -2147483648 <= #t~nondet16 && #t~nondet16 <= 2147483647;~x~0 := #t~nondet16;havoc #t~nondet16;assume -2147483648 <= #t~nondet17 && #t~nondet17 <= 2147483647;~y~0 := #t~nondet17;havoc #t~nondet17; {1224#true} is VALID [2022-04-07 12:29:31,315 INFO L272 TraceCheckUtils]: 17: Hoare triple {1224#true} call assume_abort_if_not((if ~x~0 >= 0 && ~y~0 >= 0 then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:31,315 INFO L290 TraceCheckUtils]: 18: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:31,315 INFO L290 TraceCheckUtils]: 19: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:31,315 INFO L290 TraceCheckUtils]: 20: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,315 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {1224#true} {1224#true} #79#return; {1224#true} is VALID [2022-04-07 12:29:31,315 INFO L272 TraceCheckUtils]: 22: Hoare triple {1224#true} call #t~ret18 := lcp(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0); {1224#true} is VALID [2022-04-07 12:29:31,323 INFO L290 TraceCheckUtils]: 23: Hoare triple {1224#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} is VALID [2022-04-07 12:29:31,323 INFO L290 TraceCheckUtils]: 24: Hoare triple {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} is VALID [2022-04-07 12:29:31,324 INFO L290 TraceCheckUtils]: 25: Hoare triple {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} assume #t~short7;call #t~mem5 := read~int(~a.base, ~a.offset + 4 * (~x + ~l~0), 4);call #t~mem6 := read~int(~a.base, ~a.offset + 4 * (~y + ~l~0), 4);#t~short7 := #t~mem5 == #t~mem6; {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} is VALID [2022-04-07 12:29:31,324 INFO L290 TraceCheckUtils]: 26: Hoare triple {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} assume !!#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7;#t~post8 := ~l~0;~l~0 := 1 + #t~post8;havoc #t~post8; {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} is VALID [2022-04-07 12:29:31,325 INFO L290 TraceCheckUtils]: 27: Hoare triple {1264#(and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n))} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {1265#(or |lcp_#t~short7| (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:31,325 INFO L290 TraceCheckUtils]: 28: Hoare triple {1265#(or |lcp_#t~short7| (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} assume !#t~short7; {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:31,325 INFO L290 TraceCheckUtils]: 29: Hoare triple {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} assume !#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7; {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:31,326 INFO L290 TraceCheckUtils]: 30: Hoare triple {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} #res := ~l~0; {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} is VALID [2022-04-07 12:29:31,326 INFO L290 TraceCheckUtils]: 31: Hoare triple {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} assume true; {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} is VALID [2022-04-07 12:29:31,327 INFO L284 TraceCheckUtils]: 32: Hoare quadruple {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} {1224#true} #81#return; {1250#(or (<= main_~n~0 (+ |main_#t~ret18| main_~x~0)) (<= main_~n~0 (+ |main_#t~ret18| main_~y~0)))} is VALID [2022-04-07 12:29:31,327 INFO L290 TraceCheckUtils]: 33: Hoare triple {1250#(or (<= main_~n~0 (+ |main_#t~ret18| main_~x~0)) (<= main_~n~0 (+ |main_#t~ret18| main_~y~0)))} assume -2147483648 <= #t~ret18 && #t~ret18 <= 2147483647;~l~1 := #t~ret18;havoc #t~ret18; {1251#(or (<= main_~n~0 (+ main_~l~1 main_~y~0)) (<= main_~n~0 (+ main_~l~1 main_~x~0)))} is VALID [2022-04-07 12:29:31,328 INFO L272 TraceCheckUtils]: 34: Hoare triple {1251#(or (<= main_~n~0 (+ main_~l~1 main_~y~0)) (<= main_~n~0 (+ main_~l~1 main_~x~0)))} call check(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0, ~l~1); {1252#(or (<= |check_#in~n| (+ |check_#in~x| |check_#in~l|)) (<= |check_#in~n| (+ |check_#in~y| |check_#in~l|)))} is VALID [2022-04-07 12:29:31,328 INFO L290 TraceCheckUtils]: 35: Hoare triple {1252#(or (<= |check_#in~n| (+ |check_#in~x| |check_#in~l|)) (<= |check_#in~n| (+ |check_#in~y| |check_#in~l|)))} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l := #in~l;assume -2147483648 <= #t~nondet9 && #t~nondet9 <= 2147483647;~i~0 := #t~nondet9;havoc #t~nondet9; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:31,329 INFO L272 TraceCheckUtils]: 36: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} call assume_abort_if_not((if 0 <= ~i~0 && ~i~0 < ~l then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:31,329 INFO L290 TraceCheckUtils]: 37: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:31,329 INFO L290 TraceCheckUtils]: 38: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:31,329 INFO L290 TraceCheckUtils]: 39: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,329 INFO L284 TraceCheckUtils]: 40: Hoare quadruple {1224#true} {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} #85#return; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:31,329 INFO L290 TraceCheckUtils]: 41: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} call #t~mem10 := read~int(~a.base, ~a.offset + 4 * (~x + ~i~0), 4);call #t~mem11 := read~int(~a.base, ~a.offset + 4 * (~y + ~i~0), 4); {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:31,330 INFO L272 TraceCheckUtils]: 42: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} call __VERIFIER_assert((if #t~mem10 == #t~mem11 then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:31,330 INFO L290 TraceCheckUtils]: 43: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:31,330 INFO L290 TraceCheckUtils]: 44: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:31,330 INFO L290 TraceCheckUtils]: 45: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:31,330 INFO L284 TraceCheckUtils]: 46: Hoare quadruple {1224#true} {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} #87#return; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:31,330 INFO L290 TraceCheckUtils]: 47: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} havoc #t~mem10;havoc #t~mem11; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:31,331 INFO L290 TraceCheckUtils]: 48: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} assume ~x + ~l < ~n && ~y + ~l < ~n;call #t~mem12 := read~int(~a.base, ~a.offset + 4 * (~x + ~l), 4);call #t~mem13 := read~int(~a.base, ~a.offset + 4 * (~y + ~l), 4); {1225#false} is VALID [2022-04-07 12:29:31,331 INFO L272 TraceCheckUtils]: 49: Hoare triple {1225#false} call __VERIFIER_assert((if #t~mem12 != #t~mem13 then 1 else 0)); {1225#false} is VALID [2022-04-07 12:29:31,331 INFO L290 TraceCheckUtils]: 50: Hoare triple {1225#false} ~cond := #in~cond; {1225#false} is VALID [2022-04-07 12:29:31,331 INFO L290 TraceCheckUtils]: 51: Hoare triple {1225#false} assume 0 == ~cond; {1225#false} is VALID [2022-04-07 12:29:31,331 INFO L290 TraceCheckUtils]: 52: Hoare triple {1225#false} assume !false; {1225#false} is VALID [2022-04-07 12:29:31,331 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2022-04-07 12:29:31,331 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 12:29:31,331 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [415371337] [2022-04-07 12:29:31,331 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [415371337] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-07 12:29:31,332 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [418263309] [2022-04-07 12:29:31,332 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 12:29:31,332 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 12:29:31,332 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 12:29:31,333 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 12:29:31,333 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-07 12:29:31,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:31,394 INFO L263 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 21 conjunts are in the unsatisfiable core [2022-04-07 12:29:31,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 12:29:31,445 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 12:29:32,713 INFO L272 TraceCheckUtils]: 0: Hoare triple {1224#true} call ULTIMATE.init(); {1224#true} is VALID [2022-04-07 12:29:32,713 INFO L290 TraceCheckUtils]: 1: Hoare triple {1224#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {1224#true} is VALID [2022-04-07 12:29:32,714 INFO L290 TraceCheckUtils]: 2: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:32,714 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1224#true} {1224#true} #91#return; {1224#true} is VALID [2022-04-07 12:29:32,714 INFO L272 TraceCheckUtils]: 4: Hoare triple {1224#true} call #t~ret19 := main(); {1224#true} is VALID [2022-04-07 12:29:32,714 INFO L290 TraceCheckUtils]: 5: Hoare triple {1224#true} assume -2147483648 <= #t~nondet14 && #t~nondet14 <= 2147483647;~n~0 := #t~nondet14;havoc #t~nondet14; {1224#true} is VALID [2022-04-07 12:29:32,714 INFO L272 TraceCheckUtils]: 6: Hoare triple {1224#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 < 1073741824 then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:32,714 INFO L290 TraceCheckUtils]: 7: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:32,714 INFO L290 TraceCheckUtils]: 8: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:32,714 INFO L290 TraceCheckUtils]: 9: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:32,715 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1224#true} {1224#true} #75#return; {1224#true} is VALID [2022-04-07 12:29:32,715 INFO L290 TraceCheckUtils]: 11: Hoare triple {1224#true} call #t~malloc15.base, #t~malloc15.offset := #Ultimate.allocOnHeap(4 * ~n~0); {1224#true} is VALID [2022-04-07 12:29:32,715 INFO L272 TraceCheckUtils]: 12: Hoare triple {1224#true} call #Ultimate.meminit(#t~malloc15.base, #t~malloc15.offset, ~n~0, 4, 4 * ~n~0); {1224#true} is VALID [2022-04-07 12:29:32,715 INFO L290 TraceCheckUtils]: 13: Hoare triple {1224#true} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {1224#true} is VALID [2022-04-07 12:29:32,715 INFO L290 TraceCheckUtils]: 14: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:32,715 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1224#true} {1224#true} #77#return; {1224#true} is VALID [2022-04-07 12:29:32,715 INFO L290 TraceCheckUtils]: 16: Hoare triple {1224#true} ~a~0.base, ~a~0.offset := #t~malloc15.base, #t~malloc15.offset;assume -2147483648 <= #t~nondet16 && #t~nondet16 <= 2147483647;~x~0 := #t~nondet16;havoc #t~nondet16;assume -2147483648 <= #t~nondet17 && #t~nondet17 <= 2147483647;~y~0 := #t~nondet17;havoc #t~nondet17; {1224#true} is VALID [2022-04-07 12:29:32,715 INFO L272 TraceCheckUtils]: 17: Hoare triple {1224#true} call assume_abort_if_not((if ~x~0 >= 0 && ~y~0 >= 0 then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:32,715 INFO L290 TraceCheckUtils]: 18: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:32,716 INFO L290 TraceCheckUtils]: 19: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:32,716 INFO L290 TraceCheckUtils]: 20: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:32,716 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {1224#true} {1224#true} #79#return; {1224#true} is VALID [2022-04-07 12:29:32,716 INFO L272 TraceCheckUtils]: 22: Hoare triple {1224#true} call #t~ret18 := lcp(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0); {1224#true} is VALID [2022-04-07 12:29:32,719 INFO L290 TraceCheckUtils]: 23: Hoare triple {1224#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {1340#(and (<= lcp_~y |lcp_#in~y|) (<= |lcp_#in~n| lcp_~n) (<= lcp_~x |lcp_#in~x|))} is VALID [2022-04-07 12:29:32,719 INFO L290 TraceCheckUtils]: 24: Hoare triple {1340#(and (<= lcp_~y |lcp_#in~y|) (<= |lcp_#in~n| lcp_~n) (<= lcp_~x |lcp_#in~x|))} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {1340#(and (<= lcp_~y |lcp_#in~y|) (<= |lcp_#in~n| lcp_~n) (<= lcp_~x |lcp_#in~x|))} is VALID [2022-04-07 12:29:32,720 INFO L290 TraceCheckUtils]: 25: Hoare triple {1340#(and (<= lcp_~y |lcp_#in~y|) (<= |lcp_#in~n| lcp_~n) (<= lcp_~x |lcp_#in~x|))} assume #t~short7;call #t~mem5 := read~int(~a.base, ~a.offset + 4 * (~x + ~l~0), 4);call #t~mem6 := read~int(~a.base, ~a.offset + 4 * (~y + ~l~0), 4);#t~short7 := #t~mem5 == #t~mem6; {1340#(and (<= lcp_~y |lcp_#in~y|) (<= |lcp_#in~n| lcp_~n) (<= lcp_~x |lcp_#in~x|))} is VALID [2022-04-07 12:29:32,721 INFO L290 TraceCheckUtils]: 26: Hoare triple {1340#(and (<= lcp_~y |lcp_#in~y|) (<= |lcp_#in~n| lcp_~n) (<= lcp_~x |lcp_#in~x|))} assume !!#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7;#t~post8 := ~l~0;~l~0 := 1 + #t~post8;havoc #t~post8; {1340#(and (<= lcp_~y |lcp_#in~y|) (<= |lcp_#in~n| lcp_~n) (<= lcp_~x |lcp_#in~x|))} is VALID [2022-04-07 12:29:32,721 INFO L290 TraceCheckUtils]: 27: Hoare triple {1340#(and (<= lcp_~y |lcp_#in~y|) (<= |lcp_#in~n| lcp_~n) (<= lcp_~x |lcp_#in~x|))} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {1265#(or |lcp_#t~short7| (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:32,722 INFO L290 TraceCheckUtils]: 28: Hoare triple {1265#(or |lcp_#t~short7| (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} assume !#t~short7; {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:32,722 INFO L290 TraceCheckUtils]: 29: Hoare triple {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} assume !#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7; {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:32,723 INFO L290 TraceCheckUtils]: 30: Hoare triple {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} #res := ~l~0; {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} is VALID [2022-04-07 12:29:32,723 INFO L290 TraceCheckUtils]: 31: Hoare triple {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} assume true; {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} is VALID [2022-04-07 12:29:32,727 INFO L284 TraceCheckUtils]: 32: Hoare quadruple {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} {1224#true} #81#return; {1250#(or (<= main_~n~0 (+ |main_#t~ret18| main_~x~0)) (<= main_~n~0 (+ |main_#t~ret18| main_~y~0)))} is VALID [2022-04-07 12:29:32,728 INFO L290 TraceCheckUtils]: 33: Hoare triple {1250#(or (<= main_~n~0 (+ |main_#t~ret18| main_~x~0)) (<= main_~n~0 (+ |main_#t~ret18| main_~y~0)))} assume -2147483648 <= #t~ret18 && #t~ret18 <= 2147483647;~l~1 := #t~ret18;havoc #t~ret18; {1251#(or (<= main_~n~0 (+ main_~l~1 main_~y~0)) (<= main_~n~0 (+ main_~l~1 main_~x~0)))} is VALID [2022-04-07 12:29:32,729 INFO L272 TraceCheckUtils]: 34: Hoare triple {1251#(or (<= main_~n~0 (+ main_~l~1 main_~y~0)) (<= main_~n~0 (+ main_~l~1 main_~x~0)))} call check(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0, ~l~1); {1252#(or (<= |check_#in~n| (+ |check_#in~x| |check_#in~l|)) (<= |check_#in~n| (+ |check_#in~y| |check_#in~l|)))} is VALID [2022-04-07 12:29:32,729 INFO L290 TraceCheckUtils]: 35: Hoare triple {1252#(or (<= |check_#in~n| (+ |check_#in~x| |check_#in~l|)) (<= |check_#in~n| (+ |check_#in~y| |check_#in~l|)))} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l := #in~l;assume -2147483648 <= #t~nondet9 && #t~nondet9 <= 2147483647;~i~0 := #t~nondet9;havoc #t~nondet9; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:32,729 INFO L272 TraceCheckUtils]: 36: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} call assume_abort_if_not((if 0 <= ~i~0 && ~i~0 < ~l then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:32,730 INFO L290 TraceCheckUtils]: 37: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:32,730 INFO L290 TraceCheckUtils]: 38: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:32,730 INFO L290 TraceCheckUtils]: 39: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:32,730 INFO L284 TraceCheckUtils]: 40: Hoare quadruple {1224#true} {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} #85#return; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:32,731 INFO L290 TraceCheckUtils]: 41: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} call #t~mem10 := read~int(~a.base, ~a.offset + 4 * (~x + ~i~0), 4);call #t~mem11 := read~int(~a.base, ~a.offset + 4 * (~y + ~i~0), 4); {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:32,731 INFO L272 TraceCheckUtils]: 42: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} call __VERIFIER_assert((if #t~mem10 == #t~mem11 then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:32,731 INFO L290 TraceCheckUtils]: 43: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:32,731 INFO L290 TraceCheckUtils]: 44: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:32,731 INFO L290 TraceCheckUtils]: 45: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:32,732 INFO L284 TraceCheckUtils]: 46: Hoare quadruple {1224#true} {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} #87#return; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:32,732 INFO L290 TraceCheckUtils]: 47: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} havoc #t~mem10;havoc #t~mem11; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:32,733 INFO L290 TraceCheckUtils]: 48: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} assume ~x + ~l < ~n && ~y + ~l < ~n;call #t~mem12 := read~int(~a.base, ~a.offset + 4 * (~x + ~l), 4);call #t~mem13 := read~int(~a.base, ~a.offset + 4 * (~y + ~l), 4); {1225#false} is VALID [2022-04-07 12:29:32,733 INFO L272 TraceCheckUtils]: 49: Hoare triple {1225#false} call __VERIFIER_assert((if #t~mem12 != #t~mem13 then 1 else 0)); {1225#false} is VALID [2022-04-07 12:29:32,733 INFO L290 TraceCheckUtils]: 50: Hoare triple {1225#false} ~cond := #in~cond; {1225#false} is VALID [2022-04-07 12:29:32,733 INFO L290 TraceCheckUtils]: 51: Hoare triple {1225#false} assume 0 == ~cond; {1225#false} is VALID [2022-04-07 12:29:32,733 INFO L290 TraceCheckUtils]: 52: Hoare triple {1225#false} assume !false; {1225#false} is VALID [2022-04-07 12:29:32,733 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2022-04-07 12:29:32,733 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 12:29:34,163 INFO L290 TraceCheckUtils]: 52: Hoare triple {1225#false} assume !false; {1225#false} is VALID [2022-04-07 12:29:34,163 INFO L290 TraceCheckUtils]: 51: Hoare triple {1225#false} assume 0 == ~cond; {1225#false} is VALID [2022-04-07 12:29:34,164 INFO L290 TraceCheckUtils]: 50: Hoare triple {1225#false} ~cond := #in~cond; {1225#false} is VALID [2022-04-07 12:29:34,164 INFO L272 TraceCheckUtils]: 49: Hoare triple {1225#false} call __VERIFIER_assert((if #t~mem12 != #t~mem13 then 1 else 0)); {1225#false} is VALID [2022-04-07 12:29:34,164 INFO L290 TraceCheckUtils]: 48: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} assume ~x + ~l < ~n && ~y + ~l < ~n;call #t~mem12 := read~int(~a.base, ~a.offset + 4 * (~x + ~l), 4);call #t~mem13 := read~int(~a.base, ~a.offset + 4 * (~y + ~l), 4); {1225#false} is VALID [2022-04-07 12:29:34,164 INFO L290 TraceCheckUtils]: 47: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} havoc #t~mem10;havoc #t~mem11; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:34,165 INFO L284 TraceCheckUtils]: 46: Hoare quadruple {1224#true} {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} #87#return; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:34,165 INFO L290 TraceCheckUtils]: 45: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:34,165 INFO L290 TraceCheckUtils]: 44: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:34,165 INFO L290 TraceCheckUtils]: 43: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:34,165 INFO L272 TraceCheckUtils]: 42: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} call __VERIFIER_assert((if #t~mem10 == #t~mem11 then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:34,165 INFO L290 TraceCheckUtils]: 41: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} call #t~mem10 := read~int(~a.base, ~a.offset + 4 * (~x + ~i~0), 4);call #t~mem11 := read~int(~a.base, ~a.offset + 4 * (~y + ~i~0), 4); {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:34,166 INFO L284 TraceCheckUtils]: 40: Hoare quadruple {1224#true} {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} #85#return; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:34,166 INFO L290 TraceCheckUtils]: 39: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:34,166 INFO L290 TraceCheckUtils]: 38: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:34,166 INFO L290 TraceCheckUtils]: 37: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:34,166 INFO L272 TraceCheckUtils]: 36: Hoare triple {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} call assume_abort_if_not((if 0 <= ~i~0 && ~i~0 < ~l then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:34,167 INFO L290 TraceCheckUtils]: 35: Hoare triple {1252#(or (<= |check_#in~n| (+ |check_#in~x| |check_#in~l|)) (<= |check_#in~n| (+ |check_#in~y| |check_#in~l|)))} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l := #in~l;assume -2147483648 <= #t~nondet9 && #t~nondet9 <= 2147483647;~i~0 := #t~nondet9;havoc #t~nondet9; {1253#(or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x)))} is VALID [2022-04-07 12:29:34,167 INFO L272 TraceCheckUtils]: 34: Hoare triple {1251#(or (<= main_~n~0 (+ main_~l~1 main_~y~0)) (<= main_~n~0 (+ main_~l~1 main_~x~0)))} call check(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0, ~l~1); {1252#(or (<= |check_#in~n| (+ |check_#in~x| |check_#in~l|)) (<= |check_#in~n| (+ |check_#in~y| |check_#in~l|)))} is VALID [2022-04-07 12:29:34,168 INFO L290 TraceCheckUtils]: 33: Hoare triple {1250#(or (<= main_~n~0 (+ |main_#t~ret18| main_~x~0)) (<= main_~n~0 (+ |main_#t~ret18| main_~y~0)))} assume -2147483648 <= #t~ret18 && #t~ret18 <= 2147483647;~l~1 := #t~ret18;havoc #t~ret18; {1251#(or (<= main_~n~0 (+ main_~l~1 main_~y~0)) (<= main_~n~0 (+ main_~l~1 main_~x~0)))} is VALID [2022-04-07 12:29:34,169 INFO L284 TraceCheckUtils]: 32: Hoare quadruple {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} {1224#true} #81#return; {1250#(or (<= main_~n~0 (+ |main_#t~ret18| main_~x~0)) (<= main_~n~0 (+ |main_#t~ret18| main_~y~0)))} is VALID [2022-04-07 12:29:34,169 INFO L290 TraceCheckUtils]: 31: Hoare triple {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} assume true; {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} is VALID [2022-04-07 12:29:34,169 INFO L290 TraceCheckUtils]: 30: Hoare triple {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} #res := ~l~0; {1267#(or (<= |lcp_#in~n| (+ |lcp_#in~x| |lcp_#res|)) (<= |lcp_#in~n| (+ |lcp_#in~y| |lcp_#res|)))} is VALID [2022-04-07 12:29:34,170 INFO L290 TraceCheckUtils]: 29: Hoare triple {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} assume !#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7; {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:34,170 INFO L290 TraceCheckUtils]: 28: Hoare triple {1265#(or |lcp_#t~short7| (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} assume !#t~short7; {1266#(or (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:34,171 INFO L290 TraceCheckUtils]: 27: Hoare triple {1506#(and (or (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~y| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~x| lcp_~n))) (or (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~x| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~y| lcp_~n))))} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {1265#(or |lcp_#t~short7| (<= |lcp_#in~n| (+ |lcp_#in~x| lcp_~l~0)) (<= |lcp_#in~n| (+ |lcp_#in~y| lcp_~l~0)))} is VALID [2022-04-07 12:29:34,172 INFO L290 TraceCheckUtils]: 26: Hoare triple {1506#(and (or (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~y| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~x| lcp_~n))) (or (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~x| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~y| lcp_~n))))} assume !!#t~short7;havoc #t~mem5;havoc #t~mem6;havoc #t~short7;#t~post8 := ~l~0;~l~0 := 1 + #t~post8;havoc #t~post8; {1506#(and (or (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~y| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~x| lcp_~n))) (or (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~x| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~y| lcp_~n))))} is VALID [2022-04-07 12:29:34,172 INFO L290 TraceCheckUtils]: 25: Hoare triple {1506#(and (or (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~y| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~x| lcp_~n))) (or (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~x| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~y| lcp_~n))))} assume #t~short7;call #t~mem5 := read~int(~a.base, ~a.offset + 4 * (~x + ~l~0), 4);call #t~mem6 := read~int(~a.base, ~a.offset + 4 * (~y + ~l~0), 4);#t~short7 := #t~mem5 == #t~mem6; {1506#(and (or (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~y| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~x| lcp_~n))) (or (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~x| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~y| lcp_~n))))} is VALID [2022-04-07 12:29:34,173 INFO L290 TraceCheckUtils]: 24: Hoare triple {1506#(and (or (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~y| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~x| lcp_~n))) (or (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~x| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~y| lcp_~n))))} #t~short7 := ~x + ~l~0 < ~n && ~y + ~l~0 < ~n; {1506#(and (or (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~y| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~x| lcp_~n))) (or (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~x| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~y| lcp_~n))))} is VALID [2022-04-07 12:29:34,173 INFO L290 TraceCheckUtils]: 23: Hoare triple {1224#true} ~a.base, ~a.offset := #in~a.base, #in~a.offset;~n := #in~n;~x := #in~x;~y := #in~y;~l~0 := 0; {1506#(and (or (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~y| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~x) (+ |lcp_#in~x| lcp_~n))) (or (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~x| lcp_~n)) (<= (+ |lcp_#in~n| lcp_~y) (+ |lcp_#in~y| lcp_~n))))} is VALID [2022-04-07 12:29:34,173 INFO L272 TraceCheckUtils]: 22: Hoare triple {1224#true} call #t~ret18 := lcp(~a~0.base, ~a~0.offset, ~n~0, ~x~0, ~y~0); {1224#true} is VALID [2022-04-07 12:29:34,173 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {1224#true} {1224#true} #79#return; {1224#true} is VALID [2022-04-07 12:29:34,173 INFO L290 TraceCheckUtils]: 20: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L290 TraceCheckUtils]: 19: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L290 TraceCheckUtils]: 18: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L272 TraceCheckUtils]: 17: Hoare triple {1224#true} call assume_abort_if_not((if ~x~0 >= 0 && ~y~0 >= 0 then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L290 TraceCheckUtils]: 16: Hoare triple {1224#true} ~a~0.base, ~a~0.offset := #t~malloc15.base, #t~malloc15.offset;assume -2147483648 <= #t~nondet16 && #t~nondet16 <= 2147483647;~x~0 := #t~nondet16;havoc #t~nondet16;assume -2147483648 <= #t~nondet17 && #t~nondet17 <= 2147483647;~y~0 := #t~nondet17;havoc #t~nondet17; {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1224#true} {1224#true} #77#return; {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L290 TraceCheckUtils]: 14: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L290 TraceCheckUtils]: 13: Hoare triple {1224#true} #memory_int := ~initToZeroAtPointerBaseAddress~int(#memory_int, #ptr.base); {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L272 TraceCheckUtils]: 12: Hoare triple {1224#true} call #Ultimate.meminit(#t~malloc15.base, #t~malloc15.offset, ~n~0, 4, 4 * ~n~0); {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L290 TraceCheckUtils]: 11: Hoare triple {1224#true} call #t~malloc15.base, #t~malloc15.offset := #Ultimate.allocOnHeap(4 * ~n~0); {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1224#true} {1224#true} #75#return; {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L290 TraceCheckUtils]: 9: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L290 TraceCheckUtils]: 8: Hoare triple {1224#true} assume !(0 == ~cond); {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L290 TraceCheckUtils]: 7: Hoare triple {1224#true} ~cond := #in~cond; {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L272 TraceCheckUtils]: 6: Hoare triple {1224#true} call assume_abort_if_not((if ~n~0 >= 0 && ~n~0 < 1073741824 then 1 else 0)); {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L290 TraceCheckUtils]: 5: Hoare triple {1224#true} assume -2147483648 <= #t~nondet14 && #t~nondet14 <= 2147483647;~n~0 := #t~nondet14;havoc #t~nondet14; {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L272 TraceCheckUtils]: 4: Hoare triple {1224#true} call #t~ret19 := main(); {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1224#true} {1224#true} #91#return; {1224#true} is VALID [2022-04-07 12:29:34,174 INFO L290 TraceCheckUtils]: 2: Hoare triple {1224#true} assume true; {1224#true} is VALID [2022-04-07 12:29:34,175 INFO L290 TraceCheckUtils]: 1: Hoare triple {1224#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(6, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(112, 2, 2, 1);call write~init~int(46, 2, 3, 1);call write~init~int(99, 2, 4, 1);call write~init~int(0, 2, 5, 1);call #Ultimate.allocInit(12, 3); {1224#true} is VALID [2022-04-07 12:29:34,175 INFO L272 TraceCheckUtils]: 0: Hoare triple {1224#true} call ULTIMATE.init(); {1224#true} is VALID [2022-04-07 12:29:34,175 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2022-04-07 12:29:34,175 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [418263309] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 12:29:34,175 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-04-07 12:29:34,175 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10, 10] total 14 [2022-04-07 12:29:34,175 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [705933130] [2022-04-07 12:29:34,175 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-04-07 12:29:34,176 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 3.230769230769231) internal successors, (42), 10 states have internal predecessors, (42), 4 states have call successors, (12), 5 states have call predecessors, (12), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 53 [2022-04-07 12:29:34,176 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 12:29:34,177 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 14 states, 13 states have (on average 3.230769230769231) internal successors, (42), 10 states have internal predecessors, (42), 4 states have call successors, (12), 5 states have call predecessors, (12), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-07 12:29:34,215 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 61 edges. 61 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 12:29:34,215 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-07 12:29:34,215 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 12:29:34,216 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-07 12:29:34,216 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=153, Unknown=0, NotChecked=0, Total=182 [2022-04-07 12:29:34,217 INFO L87 Difference]: Start difference. First operand 46 states and 50 transitions. Second operand has 14 states, 13 states have (on average 3.230769230769231) internal successors, (42), 10 states have internal predecessors, (42), 4 states have call successors, (12), 5 states have call predecessors, (12), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-07 12:29:35,020 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:35,020 INFO L93 Difference]: Finished difference Result 49 states and 54 transitions. [2022-04-07 12:29:35,020 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-07 12:29:35,020 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 3.230769230769231) internal successors, (42), 10 states have internal predecessors, (42), 4 states have call successors, (12), 5 states have call predecessors, (12), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 53 [2022-04-07 12:29:35,021 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 12:29:35,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 14 states, 13 states have (on average 3.230769230769231) internal successors, (42), 10 states have internal predecessors, (42), 4 states have call successors, (12), 5 states have call predecessors, (12), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-07 12:29:35,023 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 50 transitions. [2022-04-07 12:29:35,023 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 14 states, 13 states have (on average 3.230769230769231) internal successors, (42), 10 states have internal predecessors, (42), 4 states have call successors, (12), 5 states have call predecessors, (12), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-07 12:29:35,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 50 transitions. [2022-04-07 12:29:35,026 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 13 states and 50 transitions. [2022-04-07 12:29:35,070 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 50 edges. 50 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 12:29:35,071 INFO L225 Difference]: With dead ends: 49 [2022-04-07 12:29:35,071 INFO L226 Difference]: Without dead ends: 0 [2022-04-07 12:29:35,071 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 115 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=99, Invalid=407, Unknown=0, NotChecked=0, Total=506 [2022-04-07 12:29:35,073 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 55 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 326 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 358 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 326 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-07 12:29:35,073 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [57 Valid, 43 Invalid, 358 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 326 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-07 12:29:35,074 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-07 12:29:35,074 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-07 12:29:35,075 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 12:29:35,075 INFO L82 GeneralOperation]: Start isEquivalent. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-07 12:29:35,075 INFO L74 IsIncluded]: Start isIncluded. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-07 12:29:35,075 INFO L87 Difference]: Start difference. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-07 12:29:35,075 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:35,075 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-07 12:29:35,075 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-07 12:29:35,075 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 12:29:35,075 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 12:29:35,075 INFO L74 IsIncluded]: Start isIncluded. First operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand 0 states. [2022-04-07 12:29:35,075 INFO L87 Difference]: Start difference. First operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand 0 states. [2022-04-07 12:29:35,075 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 12:29:35,075 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-07 12:29:35,075 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-07 12:29:35,075 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 12:29:35,075 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 12:29:35,075 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 12:29:35,075 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 12:29:35,075 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-07 12:29:35,076 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-07 12:29:35,076 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 53 [2022-04-07 12:29:35,076 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 12:29:35,076 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-07 12:29:35,076 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 3.230769230769231) internal successors, (42), 10 states have internal predecessors, (42), 4 states have call successors, (12), 5 states have call predecessors, (12), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-07 12:29:35,076 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-07 12:29:35,076 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 12:29:35,078 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-07 12:29:35,096 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-07 12:29:35,278 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 12:29:35,280 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-04-07 12:29:35,482 INFO L882 garLoopResultBuilder]: For program point reach_errorEXIT(line 11) no Hoare annotation was computed. [2022-04-07 12:29:35,482 INFO L882 garLoopResultBuilder]: For program point reach_errorENTRY(line 11) no Hoare annotation was computed. [2022-04-07 12:29:35,482 INFO L882 garLoopResultBuilder]: For program point reach_errorFINAL(line 11) no Hoare annotation was computed. [2022-04-07 12:29:35,482 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 5 7) the Hoare annotation is: true [2022-04-07 12:29:35,482 INFO L882 garLoopResultBuilder]: For program point L6(line 6) no Hoare annotation was computed. [2022-04-07 12:29:35,482 INFO L882 garLoopResultBuilder]: For program point L6-2(lines 5 7) no Hoare annotation was computed. [2022-04-07 12:29:35,482 INFO L882 garLoopResultBuilder]: For program point assume_abort_if_notEXIT(lines 5 7) no Hoare annotation was computed. [2022-04-07 12:29:35,483 INFO L878 garLoopResultBuilder]: At program point mainENTRY(lines 35 49) the Hoare annotation is: (= |#memory_int| |old(#memory_int)|) [2022-04-07 12:29:35,483 INFO L878 garLoopResultBuilder]: At program point L45(line 45) the Hoare annotation is: (let ((.cse0 ((as const (Array Int Int)) 0))) (and (= (select |#memory_int| main_~a~0.base) .cse0) (or (<= main_~n~0 (+ main_~l~1 main_~y~0)) (<= main_~n~0 (+ main_~l~1 main_~x~0))) (= .cse0 (select |#memory_int| |main_#t~malloc15.base|)))) [2022-04-07 12:29:35,483 INFO L882 garLoopResultBuilder]: For program point mainFINAL(lines 35 49) no Hoare annotation was computed. [2022-04-07 12:29:35,483 INFO L882 garLoopResultBuilder]: For program point L44(line 44) no Hoare annotation was computed. [2022-04-07 12:29:35,483 INFO L882 garLoopResultBuilder]: For program point L45-1(line 45) no Hoare annotation was computed. [2022-04-07 12:29:35,483 INFO L878 garLoopResultBuilder]: At program point L43(line 43) the Hoare annotation is: (let ((.cse0 ((as const (Array Int Int)) 0))) (and (= (select |#memory_int| main_~a~0.base) .cse0) (= .cse0 (select |#memory_int| |main_#t~malloc15.base|)))) [2022-04-07 12:29:35,483 INFO L878 garLoopResultBuilder]: At program point L43-1(line 43) the Hoare annotation is: (let ((.cse0 ((as const (Array Int Int)) 0))) (and (= (select |#memory_int| main_~a~0.base) .cse0) (= .cse0 (select |#memory_int| |main_#t~malloc15.base|)))) [2022-04-07 12:29:35,483 INFO L882 garLoopResultBuilder]: For program point mainEXIT(lines 35 49) no Hoare annotation was computed. [2022-04-07 12:29:35,483 INFO L878 garLoopResultBuilder]: At program point L39(line 39) the Hoare annotation is: (= |#memory_int| |old(#memory_int)|) [2022-04-07 12:29:35,483 INFO L878 garLoopResultBuilder]: At program point L38(line 38) the Hoare annotation is: (= |#memory_int| |old(#memory_int)|) [2022-04-07 12:29:35,483 INFO L882 garLoopResultBuilder]: For program point L39-1(line 39) no Hoare annotation was computed. [2022-04-07 12:29:35,483 INFO L882 garLoopResultBuilder]: For program point L38-1(line 38) no Hoare annotation was computed. [2022-04-07 12:29:35,483 INFO L878 garLoopResultBuilder]: At program point L32(line 32) the Hoare annotation is: (or (not (= ((as const (Array Int Int)) 0) (select |#memory_int| |check_#in~a.base|))) (and (not (<= |check_#in~n| (+ |check_#in~x| |check_#in~l|))) (not (<= |check_#in~n| (+ |check_#in~y| |check_#in~l|))))) [2022-04-07 12:29:35,483 INFO L885 garLoopResultBuilder]: At program point checkENTRY(lines 24 33) the Hoare annotation is: true [2022-04-07 12:29:35,483 INFO L882 garLoopResultBuilder]: For program point L31(lines 31 32) no Hoare annotation was computed. [2022-04-07 12:29:35,483 INFO L882 garLoopResultBuilder]: For program point L32-1(line 32) no Hoare annotation was computed. [2022-04-07 12:29:35,483 INFO L882 garLoopResultBuilder]: For program point L31-2(lines 24 33) no Hoare annotation was computed. [2022-04-07 12:29:35,484 INFO L878 garLoopResultBuilder]: At program point L28(line 28) the Hoare annotation is: (let ((.cse0 (not (= ((as const (Array Int Int)) 0) (select |#memory_int| |check_#in~a.base|))))) (and (or .cse0 (and (not (<= |check_#in~n| (+ |check_#in~x| |check_#in~l|))) (not (<= |check_#in~n| (+ |check_#in~y| |check_#in~l|)))) (let ((.cse1 (select |#memory_int| check_~a.base)) (.cse2 (* check_~i~0 4))) (and (or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x))) (= |check_#t~mem11| |check_#t~mem10|) (= (select .cse1 (+ .cse2 (* 4 check_~x) check_~a.offset)) 0) (= (select .cse1 (+ .cse2 (* 4 check_~y) check_~a.offset)) 0)))) (or .cse0 (and (not (<= |check_#in~n| |check_#in~y|)) (not (<= |check_#in~n| |check_#in~x|))) (= check_~l 0) (not (= |check_#in~l| 0))))) [2022-04-07 12:29:35,484 INFO L878 garLoopResultBuilder]: At program point L27(line 27) the Hoare annotation is: (let ((.cse0 (not (= ((as const (Array Int Int)) 0) (select |#memory_int| |check_#in~a.base|))))) (and (or .cse0 (and (not (<= |check_#in~n| (+ |check_#in~x| |check_#in~l|))) (not (<= |check_#in~n| (+ |check_#in~y| |check_#in~l|)))) (let ((.cse1 (select |#memory_int| check_~a.base)) (.cse2 (* check_~i~0 4))) (and (or (<= check_~n (+ check_~l check_~y)) (<= check_~n (+ check_~l check_~x))) (= (select .cse1 (+ .cse2 (* 4 check_~x) check_~a.offset)) 0) (= (select .cse1 (+ .cse2 (* 4 check_~y) check_~a.offset)) 0)))) (or .cse0 (and (not (<= |check_#in~n| |check_#in~y|)) (not (<= |check_#in~n| |check_#in~x|))) (= check_~l 0) (not (= |check_#in~l| 0))))) [2022-04-07 12:29:35,484 INFO L882 garLoopResultBuilder]: For program point L28-1(line 28) no Hoare annotation was computed. [2022-04-07 12:29:35,484 INFO L882 garLoopResultBuilder]: For program point L27-1(line 27) no Hoare annotation was computed. [2022-04-07 12:29:35,484 INFO L882 garLoopResultBuilder]: For program point checkEXIT(lines 24 33) no Hoare annotation was computed. [2022-04-07 12:29:35,484 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initFINAL(line -1) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L878 garLoopResultBuilder]: At program point ULTIMATE.initENTRY(line -1) the Hoare annotation is: (and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|)) [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initEXIT(line -1) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point L18-1(line 18) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point lcpFINAL(lines 16 22) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point L18-3(lines 18 20) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L878 garLoopResultBuilder]: At program point L18-5(lines 18 20) the Hoare annotation is: (and (= |lcp_#in~x| lcp_~x) (= |lcp_#in~y| lcp_~y) (= |lcp_#in~n| lcp_~n) (= |lcp_#in~a.base| lcp_~a.base)) [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point L18-6(lines 18 20) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point lcpEXIT(lines 16 22) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L885 garLoopResultBuilder]: At program point lcpENTRY(lines 16 22) the Hoare annotation is: true [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-04-07 12:29:35,487 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startFINAL(line -1) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 12 14) the Hoare annotation is: true [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point L13(line 13) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point L13-1(line 13) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point L13-3(lines 12 14) no Hoare annotation was computed. [2022-04-07 12:29:35,487 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertEXIT(lines 12 14) no Hoare annotation was computed. [2022-04-07 12:29:35,488 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 13) no Hoare annotation was computed. [2022-04-07 12:29:35,488 INFO L878 garLoopResultBuilder]: At program point #Ultimate.meminitENTRY(line -1) the Hoare annotation is: (= |#memory_int| |old(#memory_int)|) [2022-04-07 12:29:35,488 INFO L882 garLoopResultBuilder]: For program point #Ultimate.meminitEXIT(line -1) no Hoare annotation was computed. [2022-04-07 12:29:35,488 INFO L882 garLoopResultBuilder]: For program point #Ultimate.meminitFINAL(line -1) no Hoare annotation was computed. [2022-04-07 12:29:35,490 INFO L719 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1] [2022-04-07 12:29:35,490 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-07 12:29:35,492 WARN L170 areAnnotationChecker]: reach_errorENTRY has no Hoare annotation [2022-04-07 12:29:35,493 WARN L170 areAnnotationChecker]: ULTIMATE.initFINAL has no Hoare annotation [2022-04-07 12:29:35,495 WARN L170 areAnnotationChecker]: L6 has no Hoare annotation [2022-04-07 12:29:35,495 WARN L170 areAnnotationChecker]: L13 has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: #Ultimate.meminitFINAL has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: reach_errorFINAL has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: ULTIMATE.initFINAL has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: L18-6 has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: L18-1 has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: ULTIMATE.startFINAL has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: L6 has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: L6 has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: L38-1 has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: L13 has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: L13 has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: L27-1 has no Hoare annotation [2022-04-07 12:29:35,496 WARN L170 areAnnotationChecker]: #Ultimate.meminitFINAL has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: ULTIMATE.initEXIT has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L18-6 has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L18-1 has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L18-1 has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: ULTIMATE.startFINAL has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L6-2 has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L38-1 has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L13-1 has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L13-1 has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L13-3 has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L27-1 has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: #Ultimate.meminitEXIT has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: lcpFINAL has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L18-3 has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L18-3 has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: assume_abort_if_notEXIT has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: assume_abort_if_notEXIT has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: assume_abort_if_notEXIT has no Hoare annotation [2022-04-07 12:29:35,497 WARN L170 areAnnotationChecker]: L39-1 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L28-1 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L39-1 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: lcpEXIT has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L44 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L28-1 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L32-1 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L44 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L31 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L31 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L31-2 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L45-1 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L32-1 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: checkEXIT has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: L45-1 has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: mainFINAL has no Hoare annotation [2022-04-07 12:29:35,498 WARN L170 areAnnotationChecker]: mainEXIT has no Hoare annotation [2022-04-07 12:29:35,498 INFO L163 areAnnotationChecker]: CFG has 13 edges. 13 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. 0 times interpolants missing. [2022-04-07 12:29:35,507 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 07.04 12:29:35 BoogieIcfgContainer [2022-04-07 12:29:35,507 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-07 12:29:35,508 INFO L158 Benchmark]: Toolchain (without parser) took 9528.15ms. Allocated memory was 181.4MB in the beginning and 218.1MB in the end (delta: 36.7MB). Free memory was 129.2MB in the beginning and 119.3MB in the end (delta: 9.9MB). Peak memory consumption was 45.8MB. Max. memory is 8.0GB. [2022-04-07 12:29:35,508 INFO L158 Benchmark]: CDTParser took 0.09ms. Allocated memory is still 181.4MB. Free memory was 145.8MB in the beginning and 145.6MB in the end (delta: 151.8kB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-07 12:29:35,509 INFO L158 Benchmark]: CACSL2BoogieTranslator took 203.94ms. Allocated memory is still 181.4MB. Free memory was 129.0MB in the beginning and 155.7MB in the end (delta: -26.7MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-07 12:29:35,509 INFO L158 Benchmark]: Boogie Preprocessor took 27.41ms. Allocated memory is still 181.4MB. Free memory was 155.7MB in the beginning and 153.9MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-04-07 12:29:35,509 INFO L158 Benchmark]: RCFGBuilder took 257.83ms. Allocated memory is still 181.4MB. Free memory was 153.6MB in the beginning and 139.2MB in the end (delta: 14.4MB). Peak memory consumption was 14.7MB. Max. memory is 8.0GB. [2022-04-07 12:29:35,510 INFO L158 Benchmark]: TraceAbstraction took 9035.03ms. Allocated memory was 181.4MB in the beginning and 218.1MB in the end (delta: 36.7MB). Free memory was 138.5MB in the beginning and 119.3MB in the end (delta: 19.3MB). Peak memory consumption was 56.3MB. Max. memory is 8.0GB. [2022-04-07 12:29:35,511 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - AssertionsEnabledResult: Assertions are enabled Assertions are enabled - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.09ms. Allocated memory is still 181.4MB. Free memory was 145.8MB in the beginning and 145.6MB in the end (delta: 151.8kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 203.94ms. Allocated memory is still 181.4MB. Free memory was 129.0MB in the beginning and 155.7MB in the end (delta: -26.7MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Preprocessor took 27.41ms. Allocated memory is still 181.4MB. Free memory was 155.7MB in the beginning and 153.9MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 257.83ms. Allocated memory is still 181.4MB. Free memory was 153.6MB in the beginning and 139.2MB in the end (delta: 14.4MB). Peak memory consumption was 14.7MB. Max. memory is 8.0GB. * TraceAbstraction took 9035.03ms. Allocated memory was 181.4MB in the beginning and 218.1MB in the end (delta: 36.7MB). Free memory was 138.5MB in the beginning and 119.3MB in the end (delta: 19.3MB). Peak memory consumption was 56.3MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 13]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 9 procedures, 52 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 9.0s, OverallIterations: 5, TraceHistogramMax: 3, PathProgramHistogramMax: 1, EmptinessCheckTime: 0.0s, AutomataDifference: 4.1s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.2s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 325 SdHoareTripleChecker+Valid, 1.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 317 mSDsluCounter, 221 SdHoareTripleChecker+Invalid, 1.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 62 mSDsCounter, 180 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1374 IncrementalHoareTripleChecker+Invalid, 1554 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 180 mSolverCounterUnsat, 159 mSDtfsCounter, 1374 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 248 GetRequests, 169 SyntacticMatches, 1 SemanticMatches, 78 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 115 ImplicationChecksByTransitivity, 0.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=49occurred in iteration=0, InterpolantAutomatonStates: 54, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 5 MinimizatonAttempts, 2 StatesRemovedByMinimization, 1 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 18 LocationsWithAnnotation, 46 PreInvPairs, 55 NumberOfFragments, 284 HoareAnnotationTreeSize, 46 FomulaSimplifications, 0 FormulaSimplificationTreeSizeReduction, 0.0s HoareSimplificationTime, 18 FomulaSimplificationsInter, 308 FormulaSimplificationTreeSizeReductionInter, 0.2s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.1s SatisfiabilityAnalysisTime, 3.9s InterpolantComputationTime, 283 NumberOfCodeBlocks, 283 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 329 ConstructedInterpolants, 0 QuantifiedInterpolants, 1274 SizeOfPredicates, 13 NumberOfNonLiveVariables, 231 ConjunctsInSsa, 21 ConjunctsInUnsatCore, 7 InterpolantComputations, 4 PerfectInterpolantSequences, 95/101 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 18]: Loop Invariant Derived loop invariant: ((\old(x) == x && \old(y) == y) && \old(n) == n) && a == a RESULT: Ultimate proved your program to be correct! [2022-04-07 12:29:35,544 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...