// SPDX-License-Identifier: GPL-2.0
/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */

#include <linux/bpf.h>
#include <stdbool.h>
#include <stdint.h>
#include <bpf/bpf_helpers.h>
#include "../../../include/linux/filter.h"
#include "bpf_misc.h"
#include "bpf_kfuncs.h"

#define COND_TEST(name, _initial, _step, _bound, msg, body)                     \
SEC("xdp")                                                                      \
__success                                                                       \
__log_level(2)                                                                  \
__flag(BPF_F_TEST_STATE_FREQ)                                                   \
__msg("loop header at {{[0-9]+}}, " msg)                                        \
__naked void name(void)                                                         \
{                                                                               \
	asm volatile (                                                          \
		"r6 = %[initial] ll;"                                           \
		"r7 = %[bound] ll;"                                             \
		"r9 = 0;"                                                       \
		body                                                            \
		"2: r0 = 0;"                                                    \
		"exit;"                                                         \
		:                                                               \
		: __imm_const(initial, _initial),                               \
		  __imm_const(step, _step),                                     \
		  __imm_const(bound, _bound)                                    \
		: __clobber_all);                                               \
}

/* Optional assembly runs before the tested condition, preserving its latch. */
#define PRE__COND_TEST(name, op, initial, step, bound, msg, ...)                 \
	COND_TEST(name, initial, step, bound, msg,                              \
		"1: r8 = %[step] ll;" __VA_ARGS__                               \
		"if r6 " op " r7 goto 2f;"                                      \
		"r6 += r8;"                                                     \
		"goto 1b;")

#define POST_COND_TEST(name, op, initial, step, bound, msg, ...)                \
	COND_TEST(name, initial, step, bound, msg,                              \
		"1: r8 = %[step] ll;" __VA_ARGS__                               \
		"r6 += r8;"                                                     \
		"if r6 " op " r7 goto 1b;")

/*
 * Bound fallback verification of otherwise infinite or extremely long loops.
 * JSET is not a linear condition, SCEV ignores it and the tested condition
 * alone decides the iteration count.
 */
#define LIMIT_ITERATIONS "r9 += 1; if r9 & 8 goto 2f;"

#define PRE__COND_TEST2(name, op, initial, step, bound, msg)                     \
	PRE__COND_TEST(name, op, initial, step, bound, msg, LIMIT_ITERATIONS)

#define POST_COND_TEST32(name, op, initial, step, bound, msg)                    \
	COND_TEST(name, initial, step, bound, msg,                              \
		"1: r8 = %[step] ll;" LIMIT_ITERATIONS                           \
		"w6 += w8;"                                                     \
		"if w6 " op " w7 goto 1b;")

#define ITER_U64_MAX (~0ULL)
#define ITER_S64_MAX ((1ULL << 63) - 1)
#define ITER_S64_MIN (1ULL << 63)
#define ITER_U32_MAX ((1ULL << 32) - 1)

struct map_val {
	char foo[1024];
};

struct {
	__uint(type, BPF_MAP_TYPE_HASH);
	__uint(max_entries, 1);
	__type(key, int);
	__type(value, struct map_val);
} map SEC(".maps");

typeof(map) other_map SEC(".maps");

struct {
	__uint(type, BPF_MAP_TYPE_ARRAY);
	__uint(max_entries, 1);
	__type(key, int);
	__type(value, __u64);
} small_map SEC(".maps");

struct {
	__uint(type, BPF_MAP_TYPE_RINGBUF);
	__uint(max_entries, 4096);
} ringbuf SEC(".maps");

struct {
	__uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS);
	__uint(max_entries, 1);
	__type(key, int);
	__type(value, int);
	__array(values, struct {
		__uint(type, BPF_MAP_TYPE_ARRAY);
		__uint(map_flags, BPF_F_INNER_MAP);
		__uint(max_entries, 1);
		__type(key, int);
		__type(value, struct map_val);
	});
} outer_map SEC(".maps");

struct bpf_iter__bpf_map_elem {
	struct bpf_iter_meta *meta;
	struct bpf_map *map;
	void *key;
	void *value;
};

SEC("xdp")
__success
__log_level(2)
__msg_next("scev at header 1:")
__msg_next("  r0=(+ r0 1) / (linear r0 1)")
__naked void simple_loop1(void)
{
	asm volatile ("					\
	r0 = 0;						\
loop_%=:						\
	if r0 == 10 goto exit_%=;			\
	r0 += 1;					\
	goto loop_%=;					\
exit_%=:						\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__msg("8: (7b) *(u64 *)(r1 +0) = r0     ; *fp-8 (+ *fp-8 1) -> ?")
__naked void indirect_write_invalidates_scev(void)
{
	asm volatile ("					\
	r0 = 0;						\
	*(u64 *)(r10 - 8) = r0;				\
loop_%=:						\
	r0 = *(u64 *)(r10 - 8);				\
	if r0 == 10 goto exit_%=;			\
	r0 += 1;					\
	*(u64 *)(r10 - 8) = r0;				\
	r1 = r10;					\
	r1 += -8;					\
	*(u64 *)(r1 + 0) = r0;				\
	goto loop_%=;					\
exit_%=:						\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/* Even a no-op global callee can be freplaced with one that writes to *p. */
__noinline int global_noop_counter(__u64 *p)
{
	return 0;
}

SEC("xdp")
__success
__log_level(2)
__msg("8: (85) call pc+{{[0-9]+}} {{.*}}; *fp-8 (+ *fp-8 1) -> ?")
__naked void global_call_invalidates_scev(void)
{
	asm volatile (
	"r0 = 0;"
	"*(u64 *)(r10 - 8) = r0;"
	"r6 = 0;"
"1:"
	"r0 = *(u64 *)(r10 - 8);"
	"r0 += 1;"
	"*(u64 *)(r10 - 8) = r0;"
	"r1 = r10;"
	"r1 += -8;"
	"call global_noop_counter;"
	"r6 += 1;"
	"if r6 < 3 goto 1b;"
	"r0 = 0;"
	"exit;"
	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__msg_next("scev at header 2:")
__msg_next("  *fp-8=(+ *fp-8 1) / (linear *fp-8 1)")
__msg_next(" scev at latch 3:")
__msg_next("  r0=*fp-8 / (linear *fp-8 1)")
__msg_next("  *fp-8=*fp-8 / (linear *fp-8 1)")
__naked void simple_loop2(void)
{
	asm volatile ("					\
	r0 = 0;						\
	*(u64 *)(r10 - 8) = r0;				\
loop_%=:						\
	r0 = *(u64 *)(r10 - 8);				\
	if r0 == 10 goto exit_%=;			\
	r0 = *(u64 *)(r10 - 8);				\
	r0 += 1;					\
	*(u64 *)(r10 - 8) = r0;				\
	goto loop_%=;					\
exit_%=:						\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__msg_next("scev at header 2:")
__msg_next("  r1=(+ r1 1) / (linear r1 1)")
__naked void meet_agrees(void)
{
	asm volatile ("					\
	call %[bpf_get_prandom_u32];			\
	r1 = 0;						\
1:							\
	if r1 == 2 goto 3f;				\
	if r0 == 7 goto 2f;				\
	r1 += 1;					\
	goto 1b;					\
2:							\
	r1 += 1;					\
	goto 1b;					\
3:							\
	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

SEC("xdp")
__failure
__log_level(2)
__msg_next("scev at header 1:")
__msg_next("  r6=(any r6 (+ r6 1)) / ?")
__naked void meet_disagrees(void)
{
	asm volatile ("					\
	r6 = 0;						\
1:							\
	if r6 == 2 goto 3f;				\
	call %[bpf_get_prandom_u32];			\
	if r0 == 7 goto 1b;				\
	r6 += 1;					\
	goto 1b;					\
3:							\
	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/* Both entry state values for r1 should be accounted for */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("scev at header 2:")
__msg_next("  r0=(+ r0 1) / (linear r0 1)")
__msg_next("  r1=42 / (any r1 42)")
__msg_next(" scev at latch 2:")
__msg_next("  r0=(+ r0 1) / (linear r0 1)")
__msg_next("  r1=42 / (any r1 42)")
__msg("loop header at 2, widening r0 to 0..10 step 1")
__msg_next("loop header at 2, widening r1 to 7..42 step 1")
__naked void entry_state_join(void)
{
	asm volatile ("					\
	r0 = 0;						\
	r1 = 7;						\
1:	if r0 == 10 goto 2f;	/* r1 in [7,42] */	\
	r0 += 1; 					\
	r1 = 42;					\
	goto 1b;					\
2:	r0 = r1;					\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__log_level(2)
__msg_next("scev at header 1:")
__msg_next("  r6=(bswap32 (bswap32 (zext32 (- (- (zext32 (+ (>>...) 1))))))) / ?")
__naked void expr_chain(void)
{
	asm volatile ("					\
	r6 = 0;						\
1:							\
	if r6 == 2 goto 2f;				\
	r6 += 1;					\
	r6 <<= 32;					\
	r6 >>= 32;					\
	w6 += 1;					\
	r6 = -r6;					\
	w6 = -w6;					\
	r6 = bswap32 r6;				\
	r6 = bswap32 r6;				\
	goto 1b;					\
2:							\
	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

#define ALU_OP(insn) "r1 = r6; " insn "; r0 += r1;"

SEC("xdp")
__success
__log_level(2)
__msg("r1 += 2 {{.*}}; r1 r6 -> (+ r6 2)")
__msg("r1 += r7 {{.*}}; r1 r6 -> (+ r6 r7)")
__msg("w1 += 2 {{.*}}; r1 r6 -> (zext32 (+ r6 2))")
__msg("w1 += w7 {{.*}}; r1 r6 -> (zext32 (+ r6 r7))")
__msg("r1 -= 2 {{.*}}; r1 r6 -> (- r6 2)")
__msg("r1 -= r7 {{.*}}; r1 r6 -> (- r6 r7)")
__msg("w1 -= 2 {{.*}}; r1 r6 -> (zext32 (- r6 2))")
__msg("w1 -= w7 {{.*}}; r1 r6 -> (zext32 (- r6 r7))")
__msg("r1 *= 2 {{.*}}; r1 r6 -> (* r6 2)")
__msg("r1 *= r7 {{.*}}; r1 r6 -> (* r6 r7)")
__msg("w1 *= 2 {{.*}}; r1 r6 -> (zext32 (* r6 2))")
__msg("w1 *= w7 {{.*}}; r1 r6 -> (zext32 (* r6 r7))")
__msg("r1 /= 2 {{.*}}; r1 r6 -> (/ r6 2)")
__msg("r1 /= r7 {{.*}}; r1 r6 -> (/ r6 r7)")
__msg("w1 /= 2 {{.*}}; r1 r6 -> (zext32 (/ r6 2))")
__msg("w1 /= w7 {{.*}}; r1 r6 -> (zext32 (/ r6 r7))")
__msg("r1 s/= 2 {{.*}}; r1 r6 -> (s/ r6 2)")
__msg("r1 s/= r7 {{.*}}; r1 r6 -> (s/ r6 r7)")
__msg("w1 s/= 2 {{.*}}; r1 r6 -> (zext32 (s/ r6 2))")
__msg("w1 s/= w7 {{.*}}; r1 r6 -> (zext32 (s/ r6 r7))")
__msg("r1 %= 2 {{.*}}; r1 r6 -> (% r6 2)")
__msg("r1 %= r7 {{.*}}; r1 r6 -> (% r6 r7)")
__msg("w1 %= 2 {{.*}}; r1 r6 -> (zext32 (% r6 2))")
__msg("w1 %= w7 {{.*}}; r1 r6 -> (zext32 (% r6 r7))")
__msg("r1 s%= 2 {{.*}}; r1 r6 -> (s% r6 2)")
__msg("r1 s%= r7 {{.*}}; r1 r6 -> (s% r6 r7)")
__msg("w1 s%= 2 {{.*}}; r1 r6 -> (zext32 (s% r6 2))")
__msg("w1 s%= w7 {{.*}}; r1 r6 -> (zext32 (s% r6 r7))")
__msg("r1 |= 2 {{.*}}; r1 r6 -> (| r6 2)")
__msg("r1 |= r7 {{.*}}; r1 r6 -> (| r6 r7)")
__msg("w1 |= 2 {{.*}}; r1 r6 -> (zext32 (| r6 2))")
__msg("w1 |= w7 {{.*}}; r1 r6 -> (zext32 (| r6 r7))")
__msg("r1 &= 2 {{.*}}; r1 r6 -> (& r6 2)")
__msg("r1 &= r7 {{.*}}; r1 r6 -> (& r6 r7)")
__msg("w1 &= 2 {{.*}}; r1 r6 -> (zext32 (& r6 2))")
__msg("w1 &= w7 {{.*}}; r1 r6 -> (zext32 (& r6 r7))")
__msg("r1 ^= 2 {{.*}}; r1 r6 -> (^ r6 2)")
__msg("r1 ^= r7 {{.*}}; r1 r6 -> (^ r6 r7)")
__msg("w1 ^= 2 {{.*}}; r1 r6 -> (zext32 (^ r6 2))")
__msg("w1 ^= w7 {{.*}}; r1 r6 -> (zext32 (^ r6 r7))")
__msg("r1 <<= 2 {{.*}}; r1 r6 -> (<< r6 2)")
__msg("r1 <<= r7 {{.*}}; r1 r6 -> (<< r6 r7)")
__msg("w1 <<= 2 {{.*}}; r1 r6 -> (zext32 (<< r6 2))")
__msg("w1 <<= w7 {{.*}}; r1 r6 -> (zext32 (<< r6 r7))")
__msg("r1 >>= 2 {{.*}}; r1 r6 -> (>> r6 2)")
__msg("r1 >>= r7 {{.*}}; r1 r6 -> (>> r6 r7)")
__msg("w1 >>= 2 {{.*}}; r1 r6 -> (zext32 (>> r6 2))")
__msg("w1 >>= w7 {{.*}}; r1 r6 -> (zext32 (>> r6 r7))")
__msg("r1 s>>= 2 {{.*}}; r1 r6 -> (s>> r6 2)")
__msg("r1 s>>= r7 {{.*}}; r1 r6 -> (s>> r6 r7)")
__msg("w1 s>>= 2 {{.*}}; r1 r6 -> (zext32 (s>> r6 2))")
__msg("w1 s>>= w7 {{.*}}; r1 r6 -> (zext32 (s>> r6 r7))")
__msg("r1 = -r1 {{.*}}; r1 r6 -> (- r6)")
__msg("w1 = -w1 {{.*}}; r1 r6 -> (zext32 (- r6))")
__msg("r1 = 42 {{.*}}; r1 r6 -> 42")
__msg("w1 = 42 {{.*}}; r1 r6 -> (zext32 42)")
__msg("r1 = r7 {{.*}}; r1 r6 -> r7")
__msg("w1 = w7 {{.*}}; r1 r6 -> (zext32 r7)")
__msg("r1 = (s8)r6 {{.*}}; r1 r6 -> (sext8 r6)")
__msg("r1 = (s16)r6 {{.*}}; r1 r6 -> (sext16 r6)")
__msg("r1 = (s32)r6 {{.*}}; r1 r6 -> (sext32 r6)")
__msg("w1 = (s8)w6 {{.*}}; r1 r6 -> (zext32 (sext8 r6))")
__msg("w1 = (s16)w6 {{.*}}; r1 r6 -> (zext32 (sext16 r6))")
__msg("r1 = bswap16 r1 {{.*}}; r1 r6 -> (bswap16 r6)")
__msg("r1 = bswap32 r1 {{.*}}; r1 r6 -> (bswap32 r6)")
__msg("r1 = bswap64 r1 {{.*}}; r1 r6 -> (bswap64 r6)")
#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
__msg("r1 = le16 r1 {{.*}}; r1 r6 -> (zext16 r6)")
__msg("r1 = le32 r1 {{.*}}; r1 r6 -> (zext32 r6)")
__msg("r1 += 1 {{.*}}; r1 r6 -> (+ r6 1)")
__msg("r1 = be16 r1 {{.*}}; r1 r6 -> (bswap16 r6)")
__msg("r1 = be32 r1 {{.*}}; r1 r6 -> (bswap32 r6)")
__msg("r1 = be64 r1 {{.*}}; r1 r6 -> (bswap64 r6)")
#else
__msg("r1 = le16 r1 {{.*}}; r1 r6 -> (bswap16 r6)")
__msg("r1 = le32 r1 {{.*}}; r1 r6 -> (bswap32 r6)")
__msg("r1 = le64 r1 {{.*}}; r1 r6 -> (bswap64 r6)")
__msg("r1 = be16 r1 {{.*}}; r1 r6 -> (zext16 r6)")
__msg("r1 = be32 r1 {{.*}}; r1 r6 -> (zext32 r6)")
__msg("r1 += 1 {{.*}}; r1 r6 -> (+ r6 1)")
#endif
__naked void alu_ops_exprs(void)
{
	asm volatile (
	"r6 = 7;"
	"r7 = 2;"
	"r8 = 0;"
"1:"
	"r0 = 0;"
	ALU_OP("r1 += 2")
	ALU_OP("r1 += r7")
	ALU_OP("w1 += 2")
	ALU_OP("w1 += w7")
	ALU_OP("r1 -= 2")
	ALU_OP("r1 -= r7")
	ALU_OP("w1 -= 2")
	ALU_OP("w1 -= w7")
	ALU_OP("r1 *= 2")
	ALU_OP("r1 *= r7")
	ALU_OP("w1 *= 2")
	ALU_OP("w1 *= w7")
	ALU_OP("r1 /= 2")
	ALU_OP("r1 /= r7")
	ALU_OP("w1 /= 2")
	ALU_OP("w1 /= w7")
	ALU_OP("r1 s/= 2")
	ALU_OP("r1 s/= r7")
	ALU_OP("w1 s/= 2")
	ALU_OP("w1 s/= w7")
	ALU_OP("r1 %%= 2")
	ALU_OP("r1 %%= r7")
	ALU_OP("w1 %%= 2")
	ALU_OP("w1 %%= w7")
	ALU_OP("r1 s%%= 2")
	ALU_OP("r1 s%%= r7")
	ALU_OP("w1 s%%= 2")
	ALU_OP("w1 s%%= w7")
	ALU_OP("r1 |= 2")
	ALU_OP("r1 |= r7")
	ALU_OP("w1 |= 2")
	ALU_OP("w1 |= w7")
	ALU_OP("r1 &= 2")
	ALU_OP("r1 &= r7")
	ALU_OP("w1 &= 2")
	ALU_OP("w1 &= w7")
	ALU_OP("r1 ^= 2")
	ALU_OP("r1 ^= r7")
	ALU_OP("w1 ^= 2")
	ALU_OP("w1 ^= w7")
	ALU_OP("r1 <<= 2")
	ALU_OP("r1 <<= r7")
	ALU_OP("w1 <<= 2")
	ALU_OP("w1 <<= w7")
	ALU_OP("r1 >>= 2")
	ALU_OP("r1 >>= r7")
	ALU_OP("w1 >>= 2")
	ALU_OP("w1 >>= w7")
	ALU_OP("r1 s>>= 2")
	ALU_OP("r1 s>>= r7")
	ALU_OP("w1 s>>= 2")
	ALU_OP("w1 s>>= w7")
	ALU_OP("r1 = -r1")
	ALU_OP("w1 = -w1")
	ALU_OP("r1 = 42")
	ALU_OP("w1 = 42")
	ALU_OP("r1 = r7")
	ALU_OP("w1 = w7")
	ALU_OP("r1 = (s8)r6")
	ALU_OP("r1 = (s16)r6")
	ALU_OP("r1 = (s32)r6")
	ALU_OP("w1 = (s8)w6")
	ALU_OP("w1 = (s16)w6")
	ALU_OP("r1 = bswap16 r1")
	ALU_OP("r1 = bswap32 r1")
	ALU_OP("r1 = bswap64 r1")
	ALU_OP("r1 = le16 r1")
	ALU_OP("r1 = le32 r1")
	/*
	 * Expressions unchanged by transfer() do not appear in the log.
	 * Add r1 += 1 to touch the expression and make it appear in the log.
	 */
	ALU_OP("r1 = le64 r1; r1 += 1")
	ALU_OP("r1 = be16 r1")
	ALU_OP("r1 = be32 r1")
	ALU_OP("r1 = be64 r1; r1 += 1")
	"r8 += 1;"
	"if r8 < 2 goto 1b;"
	"r0 = 0;"
	"exit;"
	::: __clobber_all);
}

#undef ALU_OP

/* Reset operands and consume results to keep transfer changes live. */
#define ST_OP(stmt)							\
	"r0 = 0; r1 = 1; r2 = 2;"					\
	"*(u64 *)(r10 - 8) = -8;"					\
	stmt ";"							\
	"r0 += r1; r0 += r2;"						\
	"r3 = *(u64 *)(r10 - 8); r0 += r3;"

SEC("xdp")
__success
__log_level(2)
__msg("*(u64 *)(r10 -8) = r1 {{.*}}; *fp-8 -8 -> 1")
__msg("*(u32 *)(r10 -8) = r1 {{.*}}; *fp-8 -8 -> (spill32 1)")
__msg("*(u16 *)(r10 -8) = r1 {{.*}}; *fp-8 -8 -> (spill16 1)")
__msg("*(u8 *)(r10 -8) = r1 {{.*}}; *fp-8 -8 -> (spill8 1)")
__msg("r1 = *(u64 *)(r10 -8) {{.*}}; r1 1 -> -8")
#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
__msg("r1 = *(u32 *)(r10 -8) {{.*}}; r1 1 -> (zext32 -8)")
__msg("r1 = *(u16 *)(r10 -8) {{.*}}; r1 1 -> (zext16 -8)")
__msg("r1 = *(u8 *)(r10 -8) {{.*}}; r1 1 -> (zext8 -8)")
__msg("r1 = *(s32 *)(r10 -8) {{.*}}; r1 1 -> (sext32 -8)")
__msg("r1 = *(s16 *)(r10 -8) {{.*}}; r1 1 -> (sext16 -8)")
__msg("r1 = *(s8 *)(r10 -8) {{.*}}; r1 1 -> (sext8 -8)")
__msg("r1 = load_acquire((u8 *)(r10 -8)) {{.*}}; r1 1 -> (zext8 -8)")
__msg("r1 = load_acquire((u16 *)(r10 -8)) {{.*}}; r1 1 -> (zext16 -8)")
__msg("r1 = load_acquire((u32 *)(r10 -8)) {{.*}}; r1 1 -> (zext32 -8)")
#else
__msg("r1 = *(u32 *)(r10 -8) {{.*}}; r1 1 -> _")
__msg("r1 = *(u16 *)(r10 -8) {{.*}}; r1 1 -> _")
__msg("r1 = *(u8 *)(r10 -8) {{.*}}; r1 1 -> _")
__msg("r1 = *(s32 *)(r10 -8) {{.*}}; r1 1 -> _")
__msg("r1 = *(s16 *)(r10 -8) {{.*}}; r1 1 -> _")
__msg("r1 = *(s8 *)(r10 -8) {{.*}}; r1 1 -> _")
__msg("r1 = load_acquire((u8 *)(r10 -8)) {{.*}}; r1 1 -> _")
__msg("r1 = load_acquire((u16 *)(r10 -8)) {{.*}}; r1 1 -> _")
__msg("r1 = load_acquire((u32 *)(r10 -8)) {{.*}}; r1 1 -> _")
#endif
__msg("r2 = load_acquire((u64 *)(r10 -8)) {{.*}}; r2 2 -> -8")
__msg("store_release((u8 *)(r10 -8), r1) {{.*}}; *fp-8 -8 -> (spill8 1)")
__msg("store_release((u16 *)(r10 -8), r1) {{.*}}; *fp-8 -8 -> (spill16 1)")
__msg("store_release((u32 *)(r10 -8), r1) {{.*}}; *fp-8 -8 -> (spill32 1)")
__msg("store_release((u64 *)(r10 -8), r1) {{.*}}; *fp-8 -8 -> 1")
__msg("lock *(u64 *)(r10 -8) += r1 {{.*}}; *fp-8 -8 -> _")
__msg("r1 = atomic64_fetch_add((u64 *)(r10 -8), r1) {{.*}}; r1 1 -> _, *fp-8 -8 -> _")
__msg("r1 = atomic_fetch_add((u32 *)(r10 -8), r1) {{.*}}; r1 1 -> _, *fp-8 -8 -> _")
__msg("r1 = atomic64_xchg((u64 *)(r10 -8), r1) {{.*}}; r1 1 -> _, *fp-8 -8 -> _")
__msg("r0 = atomic64_cmpxchg((u64 *)(r10 -8), r0, r2) {{.*}}; r0 0 -> _, *fp-8 -8 -> _")
__msg("*(u64 *)(r10 -8) = 42 {{.*}}; *fp-8 -8 -> 42")
__msg("*(u8 *)(r10 -7) = r0 {{.*}}; *fp-8 -8 -> _")
__naked void store_load_exprs(void)
{
	asm volatile (
	"r7 = 0;"
"1:"
	ST_OP("*(u64 *)(r10 - 8) = r1")
	ST_OP("*(u32 *)(r10 - 8) = r1")
	ST_OP("*(u16 *)(r10 - 8) = r1")
	ST_OP("*(u8 *)(r10 - 8) = r1")

	ST_OP("r1 = *(u64 *)(r10 - 8)")
	ST_OP("r1 = *(u32 *)(r10 - 8)")
	ST_OP("r1 = *(u16 *)(r10 - 8)")
	ST_OP("r1 = *(u8 *)(r10 - 8)")
	ST_OP("r1 = *(s32 *)(r10 - 8)")
	ST_OP("r1 = *(s16 *)(r10 - 8)")
	ST_OP("r1 = *(s8 *)(r10 - 8)")

	ST_OP(".8byte %[load_acquire8]")
	ST_OP(".8byte %[load_acquire16]")
	ST_OP(".8byte %[load_acquire32]")
	ST_OP(".8byte %[load_acquire64]")
	ST_OP(".8byte %[store_release8]")
	ST_OP(".8byte %[store_release16]")
	ST_OP(".8byte %[store_release32]")
	ST_OP(".8byte %[store_release64]")

	ST_OP(".8byte %[atomic_add64]")
	ST_OP(".8byte %[atomic_fetch_add64]")
	ST_OP(".8byte %[atomic_fetch_add32]")
	ST_OP(".8byte %[atomic_xchg64]")
	ST_OP(".8byte %[atomic_cmpxchg64]")

	ST_OP("*(u64 *)(r10 - 8) = 42")
	ST_OP("*(u8 *)(r10 - 7) = r0")

	"r7 += 1;"
	"if r7 < 2 goto 1b;"
	"r0 = 0;"
	"exit;"
	:
	: __imm_insn(atomic_add64,       BPF_ATOMIC_OP(BPF_DW, BPF_ADD,       BPF_REG_10, BPF_REG_1,  -8)),
	  __imm_insn(atomic_xchg64,      BPF_ATOMIC_OP(BPF_DW, BPF_XCHG,      BPF_REG_10, BPF_REG_1,  -8)),
	  __imm_insn(load_acquire8,      BPF_ATOMIC_OP(BPF_B,  BPF_LOAD_ACQ,  BPF_REG_1,  BPF_REG_10, -8)),
	  __imm_insn(load_acquire16,     BPF_ATOMIC_OP(BPF_H,  BPF_LOAD_ACQ,  BPF_REG_1,  BPF_REG_10, -8)),
	  __imm_insn(load_acquire32,     BPF_ATOMIC_OP(BPF_W,  BPF_LOAD_ACQ,  BPF_REG_1,  BPF_REG_10, -8)),
	  __imm_insn(load_acquire64,     BPF_ATOMIC_OP(BPF_DW, BPF_LOAD_ACQ,  BPF_REG_2,  BPF_REG_10, -8)),
	  __imm_insn(store_release8,     BPF_ATOMIC_OP(BPF_B,  BPF_STORE_REL, BPF_REG_10, BPF_REG_1,  -8)),
	  __imm_insn(store_release16,    BPF_ATOMIC_OP(BPF_H,  BPF_STORE_REL, BPF_REG_10, BPF_REG_1,  -8)),
	  __imm_insn(store_release32,    BPF_ATOMIC_OP(BPF_W,  BPF_STORE_REL, BPF_REG_10, BPF_REG_1,  -8)),
	  __imm_insn(store_release64,    BPF_ATOMIC_OP(BPF_DW, BPF_STORE_REL, BPF_REG_10, BPF_REG_1,  -8)),
	  __imm_insn(atomic_cmpxchg64,   BPF_ATOMIC_OP(BPF_DW, BPF_CMPXCHG,   BPF_REG_10, BPF_REG_2,  -8)),
	  __imm_insn(atomic_fetch_add32, BPF_ATOMIC_OP(BPF_W,  BPF_ADD | BPF_FETCH, BPF_REG_10, BPF_REG_1, -8)),
	  __imm_insn(atomic_fetch_add64, BPF_ATOMIC_OP(BPF_DW, BPF_ADD | BPF_FETCH, BPF_REG_10, BPF_REG_1, -8))
	: __clobber_all);
}

#undef ST_OP

SEC("xdp")
__success
__log_level(2)
__msg_next("scev at header 1:")
__msg_next("  r6=(+ r6 1) / (linear r6 1)")
__msg_next("  r7=?")
__msg_next(" scev at latch 1:")
__msg_next("  r6=(+ r6 1) / (linear r6 1)")
__msg_next("  r7=?")
__msg_next("scev at header 4:")
__msg_next("  r7=(+ r7 1) / (linear r7 1)")
__msg_next(" scev at latch 4:")
__msg_next("  r7=(+ r7 1) / (linear r7 1)")
__naked void nested_loop1(void)
{
	asm volatile ("					\
	r6 = 0;						\
1:							\
	if r6 == 2 goto 2f;				\
	r6 += 1;					\
	r7 = 0;						\
3:							\
	if r7 == 2 goto 4f;				\
	r7 += 1;					\
	goto 3b;					\
4:							\
	goto 1b;					\
2:							\
	r0 = r7;					\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

SEC("xdp")
__success
__msg("loop at 1")
__msg_next("  backedge from 4{{$}}")
__msg_next("  exit from 1 to 7")
__msg_next("loop at 4, nested in 1")
__msg_next("  backedge from 6, latch at 4")
__msg_next("  exit from 4 to 1")
__msg("scev at header 1:")
__msg_next("  r6=(+ r6 1) / (linear r6 1)")
__msg_next("  r7=?")
__msg_next("scev at header 4:")
__msg_next("  r7=(+ r7 1) / (linear r7 1)")
__msg_next(" scev at latch 4:")
__msg_next("  r7=(+ r7 1) / (linear r7 1)")
__msg("loop header at 1, latch not identified")
__msg("loop header at 4, widening r7 to 0..2 step 1")
__log_level(2)
__naked void nested_loop_hdr_backedge1(void)
{
	asm volatile ("					\
	r6 = 0;						\
1:							\
	if r6 == 2 goto 3f;				\
	r6 += 1;					\
	r7 = 0;						\
2:							\
	  if r7 == 2 goto 1b;				\
	  r7 += 1;					\
	  goto 2b;					\
3:							\
	r0 = r7;					\
	exit;						\
"	::: __clobber_all);
}

/*
 * Outer loop {2, 3, 4, 5} contains inner loop {3, 4, 5}.
 * The outer loop's only backedge is 4 -> 2, and its latch is also at 4,
 * inside the inner loop. Outer loop's latch index is not computed in
 * such a case, as there is no mechanism to build SCEVs for such latches
 * at the moment.
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop at 2{{$}}")
__msg_next("  backedge from 4{{$}}")
__msg_next("  exit from 5 to 6")
__msg_next("loop at 3, nested in 2")
__msg_next("  backedge from 5, latch at 5")
__msg_next("  exit from 4 to 2")
__msg_next("  exit from 5 to 6")
__msg("scev at header 2:")
__msg_next("  r6=?")
__msg_next("  r7=(+ r7 1) / (linear r7 1)")
__msg_next("scev at header 3:")
__msg_next("  r6=(+ r6 1) / (linear r6 1)")
__msg_next(" scev at latch 5:")
__msg_next("  r6=(+ r6 1) / (linear (+ r6 1) 1)")
__msg("loop header at 2, latch not identified")
__msg("loop header at 3, header_count is [0..2] ")
__naked void nested_loop_hdr_backedge2(void)
{
	asm volatile ("					\
	r6 = 0;						\
	r7 = 0;						\
1:	r7 += 1;					\
2:	r6 += 1;					\
	if r7 == 2 goto 1b;				\
	if r6 < 2 goto 2b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/*
 * Logical nest: for (r6 = 0; r6 < 3; r6++)
 *                   for (r7 = 0; r7 < 4; r7++) r8++;
 * Both backedges target header 3, so the CFG has one loop. r6 advances only
 * on the outer backedge and r7 resets there; neither has a linear SCEV.
 * r8 advances on both backedges and retains its linear SCEV.
 */
SEC("socket")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop at 3{{$}}")
__msg("scev at header 3:")
__msg_next("  r6=(any r6 (+ r6 1)) / ?")
__msg_next("  r7=(any (+ r7 1) 0) / ?")
__msg_next("  r8=(+ r8 1) / (linear r8 1)")
__msg("loop header at 3, unsupported loop: multiple backedges")
__naked void nested_loops_shared_header(void)
{
	asm volatile ("					\
	r6 = 0;						\
	r7 = 0;						\
	r8 = 0;						\
1:	r8 += 1;					\
	r7 += 1;					\
	if r7 < 4 goto 1b;				\
	r7 = 0;						\
	r6 += 1;					\
	if r6 < 3 goto 1b;				\
	r0 = r8;					\
	exit;						\
"	::: __clobber_all);
}

SEC("socket")
__success
__log_level(2)
__msg("loop header at 1, header_count is 10")
__msg("loop header at 5, header_count is 5")
__flag(BPF_F_TEST_STATE_FREQ)
__naked void nested_loops_outer_latch_true_branch_to_inner(void)
{
	asm volatile ("					\
	r0 = 0;						\
1:	r0 += 1;		/* outer loop */	\
	r1 = 0;						\
	if r0 < 10 goto 2f;	/* outer latch true branch jumps into inner loop */ \
	goto 3f;					\
2:	  r1 += 1;		/* inner loop */	\
	  if r1 < 5 goto 2b;				\
	goto 1b;					\
3:	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/*
 * Exact boundary hits for every continuation opcode.
 *
 * Example: pre_lt
 *
 *    u64 r6 = 1;
 *    while (r6 < 7) {               // r6 ∈ [1,3,5,7]
 *        r6 += 2;                   // r6 ∈ [3,5,7]
 *    }
 */
/*              name               op              initial          step             bound  expected message */
PRE__COND_TEST (pre_lt,            ">=",                 1,            2,                7, "header_count is 4 ")
POST_COND_TEST (post_lt,           "<",                  1,            2,                7, "header_count is 3 ")
PRE__COND_TEST (pre_le,            ">",                  1,            2,                7, "header_count is 5 ")
POST_COND_TEST (post_le,           "<=",                 1,            2,                7, "header_count is 4 ")
PRE__COND_TEST (pre_gt,            "<=",                 9,           -2,                3, "header_count is 4 ")
POST_COND_TEST (post_gt,           ">",                  9,           -2,                3, "header_count is 3 ")
PRE__COND_TEST (pre_ge,            "<",                  9,           -2,                3, "header_count is 5 ")
POST_COND_TEST (post_ge,           ">=",                 9,           -2,                3, "header_count is 4 ")
PRE__COND_TEST (pre_slt,           "s>=",               -5,            2,                1, "header_count is 4 ")
POST_COND_TEST (post_slt,          "s<",                -5,            2,                1, "header_count is 3 ")
PRE__COND_TEST (pre_sle,           "s>",                -5,            2,                1, "header_count is 5 ")
POST_COND_TEST (post_sle,          "s<=",               -5,            2,                1, "header_count is 4 ")
PRE__COND_TEST (pre_sgt,           "s<=",                5,           -2,               -1, "header_count is 4 ")
POST_COND_TEST (post_sgt,          "s>",                 5,           -2,               -1, "header_count is 3 ")
PRE__COND_TEST (pre_sge,           "s<",                 5,           -2,               -1, "header_count is 5 ")
POST_COND_TEST (post_sge,          "s>=",                5,           -2,               -1, "header_count is 4 ")
PRE__COND_TEST (pre_ne,            "==",                 1,            2,                7, "header_count is 4 ")
POST_COND_TEST (post_ne,           "!=",                 1,            2,                7, "header_count is 3 ")
PRE__COND_TEST (pre_ne_down,       "==",                 9,           -2,                3, "header_count is 4 ")
POST_COND_TEST (post_ne_down,      "!=",                 9,           -2,                3, "header_count is 3 ")

/*
 * Bounds between two consecutive counter values.
 *
 * Example: pre_lt_round
 *
 *    u64 r6 = 1;
 *    while (r6 < 8) {               // r6 ∈ [1,3,5,7,9]
 *        r6 += 2;                   // r6 ∈ [3,5,7,9]
 *    }
 */
PRE__COND_TEST (pre_lt_round,      ">=",                 1,            2,                8, "header_count is 5 ")
PRE__COND_TEST (pre_le_round,      ">",                  1,            2,                8, "header_count is 5 ")
PRE__COND_TEST (pre_gt_round,      "<=",                 9,           -2,                2, "header_count is 5 ")
PRE__COND_TEST (pre_ge_round,      "<",                  9,           -2,                2, "header_count is 5 ")
PRE__COND_TEST (pre_slt_round,     "s>=",               -5,            2,                2, "header_count is 5 ")
PRE__COND_TEST (pre_sle_round,     "s>",                -5,            2,                2, "header_count is 5 ")
PRE__COND_TEST (pre_sgt_round,     "s<=",                5,           -2,               -2, "header_count is 5 ")
PRE__COND_TEST (pre_sge_round,     "s<",                 5,           -2,               -2, "header_count is 5 ")

/*
 * Equality on the first non-strict comparison still takes a backedge.
 *
 * Example: pre_le_eq
 *
 *    u64 r6 = 7;
 *    while (r6 <= 7) {              // r6 ∈ [7,9]
 *        r6 += 2;                   // r6 ∈ [9]
 *    }
 */
PRE__COND_TEST (pre_le_eq,         ">",                  7,            2,                7, "header_count is 2 ")
PRE__COND_TEST (pre_ge_eq,         "<",                  3,           -2,                3, "header_count is 2 ")
PRE__COND_TEST (pre_sle_eq,        "s>",                 1,            2,                1, "header_count is 2 ")
PRE__COND_TEST (pre_sge_eq,        "s<",                -1,           -2,               -1, "header_count is 2 ")

/*
 * Unsigned order across the sign bit.
 *
 * Example: pre_lt_sign
 *
 *    u64 H = 1ULL << 63, r6 = H - 2;
 *    while (r6 < H + 1) {           // r6 ∈ [H-2,H-1,H,H+1]
 *        r6 += 1;                   // r6 ∈ [H-1,H,H+1]
 *    }
 */
PRE__COND_TEST (pre_lt_sign,       ">=",  ITER_S64_MAX - 1,            1, ITER_S64_MIN + 1, "header_count is 4 ")
PRE__COND_TEST (pre_gt_sign,       "<=",  ITER_S64_MIN + 1,           -1, ITER_S64_MAX - 1, "header_count is 4 ")

/*
 * The first latch comparison is false.
 *
 * Example: pre_lt_false
 *
 *    u64 r6 = 7;
 *    while (r6 < 7) {               // r6 ∈ [7]
 *        r6 += 2;                   // unreachable
 *    }
 */
PRE__COND_TEST (pre_lt_false,      ">=",                 7,            2,                7, "can't compute iterations count")
PRE__COND_TEST (pre_le_false,      ">",                  8,            2,                7, "can't compute iterations count")
PRE__COND_TEST (pre_gt_false,      "<=",                 3,           -2,                3, "can't compute iterations count")
PRE__COND_TEST (pre_ge_false,      "<",                  2,           -2,                3, "can't compute iterations count")
PRE__COND_TEST (pre_slt_false,     "s>=",                1,            2,                1, "can't compute iterations count")
PRE__COND_TEST (pre_sle_false,     "s>",                 2,            2,                1, "can't compute iterations count")
PRE__COND_TEST (pre_sgt_false,     "s<=",               -1,           -2,               -1, "can't compute iterations count")
PRE__COND_TEST (pre_sge_false,     "s<",                -2,           -2,               -1, "can't compute iterations count")
PRE__COND_TEST (pre_ne_false,      "==",                 7,            2,                7, "can't compute iterations count")

/*
 * The counter moves away from the exit; bound fallback verification.
 *
 * Example: pre_lt_dir
 *
 *    u64 r6 = 5, r9 = 0;
 *    while (++r9 <= 8 && r6 < 7) {  // r6 ∈ [5,3,1,U64_MAX]
 *        r6 -= 2;                   // r6 ∈ [3,1,U64_MAX]
 *    }
 */
PRE__COND_TEST2(pre_lt_dir,        ">=",                 5,           -2,                7, "can't compute iterations count")
PRE__COND_TEST2(pre_le_dir,        ">",                  5,           -2,                7, "can't compute iterations count")
PRE__COND_TEST2(pre_gt_dir,        "<=",                 5,            2,                3, "can't compute iterations count")
PRE__COND_TEST2(pre_ge_dir,        "<",                  5,            2,                3, "can't compute iterations count")
PRE__COND_TEST2(pre_slt_dir,       "s>=",               -1,           -2,                1, "can't compute iterations count")
PRE__COND_TEST2(pre_sle_dir,       "s>",                -1,           -2,                1, "can't compute iterations count")
PRE__COND_TEST2(pre_sgt_dir,       "s<=",                1,            2,               -1, "can't compute iterations count")
PRE__COND_TEST2(pre_sge_dir,       "s<",                 1,            2,               -1, "can't compute iterations count")

/*
 * The predicted exit would wrap the counter.
 *
 * Example: pre_lt_wrap
 *
 *    u64 M = U64_MAX, r6 = M - 1, r9 = 0;
 *    while (++r9 <= 8 && r6 < M) {  // r6 ∈ [M-1,0,2,...,14]
 *        r6 += 2;                   // r6 ∈ [0,2,...,14]
 *    }
 */
PRE__COND_TEST2(pre_lt_wrap,       ">=",  ITER_U64_MAX - 1,            2,     ITER_U64_MAX, "can't compute iterations count")
PRE__COND_TEST2(pre_le_wrap,       ">",       ITER_U64_MAX,            1,     ITER_U64_MAX, "can't compute iterations count")
PRE__COND_TEST2(pre_gt_wrap,       "<=",                 1,           -2,                0, "can't compute iterations count")
PRE__COND_TEST2(pre_ge_wrap,       "<",                  0,           -1,                0, "can't compute iterations count")
PRE__COND_TEST2(pre_slt_wrap,      "s>=", ITER_S64_MAX - 1,            2,     ITER_S64_MAX, "can't compute iterations count")
PRE__COND_TEST2(pre_sle_wrap,      "s>",      ITER_S64_MAX,            1,     ITER_S64_MAX, "can't compute iterations count")
PRE__COND_TEST2(pre_sgt_wrap,      "s<=", ITER_S64_MIN + 1,           -2,     ITER_S64_MIN, "can't compute iterations count")
PRE__COND_TEST2(pre_sge_wrap,      "s<",      ITER_S64_MIN,           -1,     ITER_S64_MIN, "can't compute iterations count")

/*
 * The non-strict count itself would overflow u64.
 *
 * Example: pre_le_count_ovf
 *
 *    u64 r6 = 0, r9 = 0;
 *    while (++r9 <= 8 && r6 <= U64_MAX) {  // r6 ∈ [0..8]
 *        r6 += 1;                         // r6 ∈ [1..8]
 *    }
 */
PRE__COND_TEST2(pre_le_count_ovf,  ">",                  0,            1,     ITER_U64_MAX, "can't compute iterations count")
PRE__COND_TEST2(pre_ge_count_ovf,  "<",       ITER_U64_MAX,           -1,                0, "can't compute iterations count")
PRE__COND_TEST2(pre_sle_count_ovf, "s>",      ITER_S64_MIN,            1,     ITER_S64_MAX, "can't compute iterations count")
PRE__COND_TEST2(pre_sge_count_ovf, "s<",      ITER_S64_MAX,           -1,     ITER_S64_MIN, "can't compute iterations count")

/*
 * JNE divisibility and equality across unsigned wraparound.
 *
 * Example: pre_ne_rem
 *
 *    u64 r6 = 1, r9 = 0;
 *    while (++r9 <= 8 && r6 != 8) { // r6 ∈ [1,3,...,17]
 *        r6 += 2;                   // r6 ∈ [3,5,...,17]
 *    }
 */
PRE__COND_TEST2(pre_ne_rem,        "==",                 1,            2,                8, "can't compute iterations count")
PRE__COND_TEST2(pre_ne_rem_down,   "==",                 9,           -2,                2, "can't compute iterations count")
PRE__COND_TEST (pre_ne_wrap_up,    "==",  ITER_U64_MAX - 1,            2,                0, "header_count is 2 ")
PRE__COND_TEST (pre_ne_wrap_down,  "==",                 1,           -2,     ITER_U64_MAX, "header_count is 2 ")

/*
 * Largest supported header count, sentinel, and u32 overflow.
 *
 * Example: pre_lt_max_hdrs
 *
 *    u64 r6 = 0, r9 = 0;
 *    while (++r9 <= 8 && r6 < U32_MAX - 2) { // r6 ∈ [0..8]
 *        r6 += 1;                            // r6 ∈ [1..8]
 *    }
 */
PRE__COND_TEST2(pre_lt_max_hdrs,   ">=",                 0,            1, ITER_U32_MAX - 2, "header_count is [0..4294967294] ")
PRE__COND_TEST2(pre_lt_sentinel,   ">=",                 0,            1, ITER_U32_MAX - 1, "can't compute iterations count")
PRE__COND_TEST2(pre_lt_hdr_ovf,    ">=",                 0,            1,     ITER_U32_MAX, "can't compute iterations count")

/*
 * The extreme signed step values remain valid unsigned magnitudes.
 *
 * Example: pre_lt_step_max
 *
 *    u64 r6 = 0;
 *    while (r6 < S64_MAX) {         // r6 ∈ [0,S64_MAX]
 *        r6 += S64_MAX;             // r6 ∈ [S64_MAX]
 *    }
 */
PRE__COND_TEST (pre_lt_step_max,   ">=",                 0, ITER_S64_MAX,     ITER_S64_MAX, "header_count is 2 ")
PRE__COND_TEST (pre_gt_step_min,   "<=",      ITER_S64_MIN, ITER_S64_MIN,                0, "header_count is 2 ")
PRE__COND_TEST (pre_ne_step_min,   "==",                 0, ITER_S64_MIN,     ITER_S64_MIN, "header_count is 2 ")

/*
 * A zero step cannot establish a finite iteration count.
 *
 * Example: pre_lt_zero_step
 *
 *    u64 r6 = 1, r9 = 0;
 *    while (++r9 <= 8 && r6 < 7) {  // r6 ∈ [1], nine header visits
 *        r6 += 0;                   // r6 ∈ [1]
 *    }
 */
PRE__COND_TEST2(pre_lt_zero_step,  ">=",                 1,            0,                7, "can't compute iterations count")

/*
 * Signed JMP32 comparisons sign-extend the initial value, bound and step.
 * Encode negative operands as positive u32 constants so the conversion matters.
 * post32_sgt also checks that an exit exactly at S32_MIN is accepted.
 */
/*              name               op                 initial  step             bound  expected message */
POST_COND_TEST32(post32_slt,       "s<",                  -7u,    2,              -1u, "header_count is [0..3] ")
POST_COND_TEST32(post32_sle,       "s<=",                 -7u,    2,              -1u, "header_count is [0..4] ")
POST_COND_TEST32(post32_sgt,       "s>", (__u32)INT32_MIN + 6,  -2u, (__u32)INT32_MIN, "header_count is [0..3] ")
POST_COND_TEST32(post32_sge,       "s>=",                 -1u,  -2u,              -7u, "header_count is [0..4] ")

/*
 * When computing 32-bit iteration bounds, scev.c:compute_max_iters() does
 * the computation in the 64-bit domain first. For unsigned JMP32 comparisons,
 * it zero-extends the initial value and bound, but sign-extends the step.
 * Hence pick negative 64-bit initial values and bounds, and encode negative
 * steps as positive u32 constants, so both conversions affect the computation.
 * post32_lt also checks that an exit exactly at U32_MAX is accepted.
 */
POST_COND_TEST32(post32_lt,        "<",                    -7,    2,               -1, "header_count is [0..3] ")
POST_COND_TEST32(post32_le,        "<=",                   -9,    2,               -3, "header_count is [0..4] ")
POST_COND_TEST32(post32_gt,        ">",                    -1,  -2u,               -7, "header_count is [0..3] ")
POST_COND_TEST32(post32_ge,        ">=",                   -1,  -2u,               -7, "header_count is [0..4] ")
POST_COND_TEST32(post32_ne,        "!=",                   -1,  -2u,               -7, "header_count is [0..3] ")

/* An exit exactly at S32_MAX is accepted as well. */
POST_COND_TEST32(post32_slt_max,   "s<",        INT32_MAX - 6,    2,        INT32_MAX, "header_count is [0..3] ")

/*
 * The first iteration fits in 32 bits, but the predicted exit overshoots the bound
 * by one and wraps.
 */
POST_COND_TEST32(post32_slt_wrap,  "s<",        INT32_MAX - 3,    2,        INT32_MAX, "can't compute iterations count")
POST_COND_TEST32(post32_sgt_wrap,  "s>", (__u32)INT32_MIN + 3,  -2u, (__u32)INT32_MIN, "can't compute iterations count")
POST_COND_TEST32(post32_lt_wrap,   "<",                    -4,    2,               -1, "can't compute iterations count")

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 1, header_count is 10 ")
__msg("loop header at 1, widening r0 to 0..9 step 1")
__msg("processed 5 insns")
__naked void post_cond_jlt(void)
{
	asm volatile ("					\
	r0 = 0;						\
1:	r0 += 1;					\
	if r0 < 10 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

/*
 * Explore with r7=10 first, r7=4096 next.
 * Should trigger invalid stack read if r7 is marked precise.
 *
 *   r0 = 0;
 *   r6 = 0;
 *   r7 = bpf_get_prandom_u32() == 42 ? 10 : 4096;
 *   do {
 *           r0++;
 *           r6++;
 *           r3 = *(fp - r0);
 *   } while (r6 < r7);
 *   return r0;
 */
SEC("xdp")
__failure
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 6, header_count is 10 ")
__msg("mark_precise: frame0: parent state regs=r6,r7 stack=:")
__msg("loop header at 6, widening r0 to 0..9 step 1")
__msg("loop header at 6, header_count is 4096 ")
__msg("loop header at 6, widening r0 to 0..4095 step 1")
__msg("invalid variable-offset read from stack R2")
__naked void mark_bound_precise(void)
{
	asm volatile ("					\
	call %[bpf_get_prandom_u32];			\
	r7 = 4096;					\
	if r0 != 42 goto 1f;				\
	r7 = 10;					\
1:	r0 = 0;						\
	r6 = 0;						\
2:	r0 += 1;					\
	r6 += 1;					\
	r2 = r0;					\
	r2 = -r2;					\
	r2 += r10;					\
	r3 = *(u8 *)(r2 + 0);				\
	if r6 < r7 goto 2b;				\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * Explore with r6=4086 first, r6=0 next.
 * Should trigger invalid stack read if r6 is marked precise.
 *
 *   r0 = 0;
 *   r6 = bpf_get_prandom_u32() == 42 ? 4086 : 0;
 *   do {
 *           r0++;
 *           r6++;
 *           r3 = *(fp - r0);
 *   } while (r6 < 4096);
 *   return r0;
 */
SEC("xdp")
__failure
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 5, header_count is 10 ")
__msg("mark_precise: frame0: parent state regs=r6 stack=:")
__msg("loop header at 5, widening r0 to 0..9 step 1")
__msg("loop header at 5, header_count is 4096 ")
__msg("loop header at 5, widening r0 to 0..4095 step 1")
__msg("invalid variable-offset read from stack R2")
__naked void mark_base_precise(void)
{
	asm volatile ("					\
	call %[bpf_get_prandom_u32];			\
	r6 = 0;						\
	if r0 != 42 goto 1f;				\
	r6 = 4086;					\
1:	r0 = 0;						\
2:	r0 += 1;					\
	r6 += 1;					\
	r2 = r0;					\
	r2 = -r2;					\
	r2 += r10;					\
	r3 = *(u8 *)(r2 + 0);				\
	if r6 < 4096 goto 2b;				\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * Spill size should be taken into account when evaluating bound scev.
 *
 *   r0 = 256;
 *   *(u8 *)(r10 - 8) = r0;
 *   r0 = 0;
 *   do {
 *           r0++;
 *           r1 = *(u64 *)(r10 - 8);
 *           if (r0 & 0x200) break; // hidden from scev, limit main pass iterations.
 *   } while (r0 < r1);
 *   return r0;
 */
SEC("xdp")
__success
__log_level(2)
__msg("scev at header 3:")
__msg_next("  r0=(+ r0 1) / (linear r0 1)")
__msg("loop header at 3, can't compute iterations count")
__naked void eval_expr_small_spill_bound(void)
{
	asm volatile ("					\
	r0 = 256;					\
	*(u8 *)(r10 - 8) = r0;				\
	r0 = 0;						\
1:	r0 += 1;					\
	r1 = *(u64 *)(r10 - 8);				\
	if r0 & 0x200 goto 2f;				\
	if r0 < r1 goto 1b;				\
2:	exit;						\
"	::: __clobber_all);
}

/* Even when the saved value fits, the upper bytes of the slot are unknown. */
SEC("xdp")
__success
__log_level(2)
__msg("scev at header 3:")
__msg_next("  r0=(+ r0 1) / (linear r0 1)")
__msg("loop header at 3, can't compute iterations count")
__naked void eval_expr_small_spill_bound_fits(void)
{
	asm volatile ("					\
	r0 = 10;					\
	*(u8 *)(r10 - 8) = r0;				\
	r0 = 0;						\
1:	r0 += 1;					\
	r1 = *(u64 *)(r10 - 8);				\
	if r0 & 0x80 goto 2f;				\
	if r0 < r1 goto 1b;				\
2:	exit;						\
"	::: __clobber_all);
}

/*
 *   r0 = 255;
 *   *(u8 *)(r10 - 8) = r0;		// narrow spill
 *   do {
 *           r0 = *(u64 *)(r10 - 8);	// wide load, widening should bail out here.
 *           r0++;
 *           *(u64 *)(r10 - 8) = r0;
 *   } while (r0 < 265);
 *   return r0;
 */
SEC("xdp")
__success
__log_level(2)
__msg("scev at header 2:")
__msg_next("  *fp-8=(+ *fp-8 1) / (linear *fp-8 1)")
__msg("loop header at 2, can't compute iterations count")
__not_msg("widening")
__naked void no_widen_small_spill_counter(void)
{
	asm volatile ("					\
	r0 = 255;					\
	*(u8 *)(r10 - 8) = r0;				\
1:	r0 = *(u64 *)(r10 - 8);				\
	r0 += 1;					\
	*(u64 *)(r10 - 8) = r0;				\
	if r0 < 265 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

/* Full-width counterpart: the counter can be widened from 5 to 14. */
SEC("xdp")
__success
__log_level(2)
__msg("scev at header 2:")
__msg_next("  *fp-8=(+ *fp-8 1) / (linear *fp-8 1)")
__msg("loop header at 2, widening *fp-8 to 5..14 step 1")
__naked void widen_full_spill_counter(void)
{
	asm volatile ("					\
	r0 = 5;						\
	*(u64 *)(r10 - 8) = r0;				\
1:	r0 = *(u64 *)(r10 - 8);				\
	r0 += 1;					\
	*(u64 *)(r10 - 8) = r0;				\
	if r0 < 15 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__msg("scev at header 2:")
__msg_next("  *fp-8=(+ *fp-8 1) / (linear *fp-8 1)")
__msg("loop header at 2, widening *fp-8 to 5..14 step 1")
__naked void widen_acquire_release_counter(void)
{
	asm volatile (
	"r0 = 5;"
	"*(u64 *)(r10 - 8) = r0;"
"1:"
	".8byte %[load_acquire];"
	"r0 += 1;"
	".8byte %[store_release];"
	"if r0 < 15 goto 1b;"
	"exit;"
	:
	: __imm_insn(load_acquire, BPF_ATOMIC_OP(BPF_DW, BPF_LOAD_ACQ, BPF_REG_0, BPF_REG_10, -8)),
	  __imm_insn(store_release, BPF_ATOMIC_OP(BPF_DW, BPF_STORE_REL, BPF_REG_10, BPF_REG_0, -8))
	: __clobber_all);
}

/*
 * r6 scev is (any r6 *fp-8). The byte store leaves memory at zero,
 * but the spill metadata retains 256. Widen r6 to an unknown scalar
 * instead of [1,256], which would exclude the zero loaded from memory.
 *
 *   r0 = 0;
 *   *(u64 *)(r10 - 8) = r0;
 *   r0 = 256;
 *   *(u8 *)(r10 - 8) = r0;		// narrow spill
 *   r6 = 1;
 *   r7 = 0;
 *   do {
 *           r0 = r6;
 *           r6 = *(u64 *)(r10 - 8);
 *           r7++;
 *   } while (r7 < 2);
 *   return r0;
 */
SEC("xdp")
__success __retval(0)
__log_level(2)
__msg("scev at header 6:")
__msg_next("  r6=*fp-8 / (any r6 *fp-8)")
__msg_next("  r7=(+ r7 1) / (linear r7 1)")
__msg("loop header at 6, widening r6 to 0x8000000000000000..0x7fffffffffffffff step 1")
__naked void widen_any_small_spill_leaf(void)
{
	asm volatile ("					\
	r0 = 0;						\
	*(u64 *)(r10 - 8) = r0;				\
	r0 = 256;					\
	*(u8 *)(r10 - 8) = r0;				\
	r6 = 1;						\
	r7 = 0;						\
1:	r0 = r6;					\
	r6 = *(u64 *)(r10 - 8);				\
	r7 += 1;					\
	if r7 < 2 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

/*
 * Widening (any *fp-8 7) must allocate the slot before writing its state.
 * The unallocated entry value makes the union an unknown scalar.
 *
 *   r6 = 0;
 *   do {
 *           if (r6 == 1)
 *                   *(u64 *)(r10 - 8) = 7;
 *           r0 = *(u64 *)(r10 - 8);
 *           r6++;
 *   } while (r6 < 3);
 *   return r0;
 */
SEC("xdp")
__success __retval(7)
__log_level(2)
__msg("scev at header 1:")
__msg_next("r6=(+ r6 1) / (linear r6 1)")
__msg_next("*fp-8=(any *fp-8 7) / (any *fp-8 7)")
__msg("loop header at 1, widening r6 to 0..2 step 1")
__msg("2: (7a) *(u64 *)(r10 -8) = 7          ; R10=fp0 fp-8=7 loop_stack=1")
__naked void widen_any_unallocated_slot(void)
{
	asm volatile ("					\
	r6 = 0;						\
1:	if r6 != 1 goto 2f;				\
	*(u64 *)(r10 - 8) = 7;				\
2:	r0 = *(u64 *)(r10 - 8);				\
	r6 += 1;					\
	if r6 < 3 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

/* A spilled zero entry contributes zero to the union. */
SEC("xdp")
__success __retval(7)
__log_level(2)
__msg("loop header at 2, widening *fp-8 to 0..7 step 1")
__naked void widen_any_zero_spill(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r6 = 0;						\
1:	if r6 != 1 goto 2f;				\
	*(u64 *)(r10 - 8) = 7;				\
2:	r0 = *(u64 *)(r10 - 8);				\
	r6 += 1;					\
	if r6 < 3 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

/* A byte store inside the slot leaves STACK_MISC and an unknown scalar value. */
SEC("xdp")
__success __retval(7)
__log_level(2)
__msg("scev at header 2:")
__msg_next("r6=(+ r6 1) / (linear r6 1)")
__msg_next("*fp-8=(any *fp-8 7) / (any *fp-8 7)")
__msg("loop header at 2, widening r6 to 0..2 step 1")
__msg("3: (79) r1 = *(u64 *)(r10 -8)         ; R1=scalar() R10=fp0 fp-8=m???????")
__naked void widen_any_misc_slot(void)
{
	asm volatile ("					\
	*(u8 *)(r10 - 1) = 1;				\
	r6 = 0;						\
1:	if r6 != 1 goto 2f;				\
	r1 = *(u64 *)(r10 - 8);				\
	*(u64 *)(r10 - 8) = 7;				\
2:	r0 = *(u64 *)(r10 - 8);				\
	r6 += 1;					\
	if r6 < 3 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

__naked __noinline __used static int probe_read_stack(void)
{
	asm volatile (
	"r2 = 8;"
	"r3 = 0;"
	"call %[bpf_probe_read_kernel];"
	"exit;"
	:
	: __imm(bpf_probe_read_kernel)
	: __clobber_all);
}

/*
 * r3 = r8 + 4 is linked to r8 when it enters the loop. Widening drops the link. If
 * it leaves the 4 behind then r4 = r3 + 1 is taken for r3 - 3 when r3 is compared:
 * r4 <= 7 instead of r4 <= 11, and the read of r9 looks like dead code.
 */
SEC("socket")
__failure __msg("R9 !read_ok")
__naked void widened_reg_is_not_linked(void)
{
	asm volatile (
	"call %[bpf_get_prandom_u32];"
	"r8 = r0;"
	"r8 &= 0xff;"
	"r3 = r8;"
	"r3 += 4;"
	"r1 = 0;"
"1:"
	"r4 = r3;"
	"r4 += 1;"
	"if r3 > 10 goto 3f;"
	"if r4 <= 7 goto 2f;"
	"r0 = *(u64 *)(r9 + 0);"
"2:"
	"r3 += 1;"
	"r1 += 1;"
	"if r1 < 2 goto 1b;"
"3:"
	"r0 = r8;"
	"exit;"
	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/* The unknown SCEV of an unbound STACK_MISC slot must not prevent widening. */
SEC("tracepoint")
__success
__log_level(2)
__msg("scev at header 4:")
__msg_next("  r6=(+ r6 1) / (linear r6 1)")
__msg_next("  *fp-8=?")
__msg("loop header at 4, widening r6 to 0..9 step 1")
__naked void widen_subprog_probe_read(void)
{
	asm volatile (
	"r1 = r10;"
	"r1 += -8;"
	"call probe_read_stack;"
	"r6 = 0;"
"1:"
	"r0 = *(u64 *)(r10 - 8);"
	"r1 = r10;"
	"r1 += -8;"
	"call probe_read_stack;"
	"r6 += 1;"
	"if r6 < 10 goto 1b;"
	"r0 = 0;"
	"exit;"
	::: __clobber_all);
}

/* An induction variable whose range overflows s64 is widened to the full range. */
SEC("socket")
__success
__log_level(2)
__msg("loop header at 4, header_count is 10")
__msg("loop header at 4, widening r1 to 0..9 step 1")
__msg("loop header at 4, widening r6 to 0x8000000000000000..0x7fffffffffffffff step 1")
__flag(BPF_F_TEST_STATE_FREQ)
__naked void widen_overflowing_range(void)
{
	asm volatile ("					\
	call %[bpf_get_prandom_u32];			\
	r6 = r0;					\
	r6 |= 1;	/* not an unknown scalar, those need no widening */	\
	r1 = 0;						\
1:	r6 += 24;					\
	r1 += 1;					\
	if r1 < 10 goto 1b;				\
	r0 = r6;					\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * The bound slot is unallocated at the first loop header. SCEV must
 * treat it as an unknown scalar. JSET limits main-pass iterations.
 *
 *   r0 = 0;
 *   do {
 *           r0++;
 *           r1 = *(u64 *)(r10 - 8);
 *           if (r0 & 0x80) break;
 *   } while (r0 < r1);
 *   return 0;
 */
SEC("xdp")
__success __retval(0)
__log_level(2)
__msg("scev at header 1:")
__msg_next("  r0=(+ r0 1) / (linear r0 1)")
__msg("loop header at 1, can't compute iterations count")
__not_msg("widening")
__naked void eval_expr_unallocated_stack_bound(void)
{
	asm volatile ("					\
	r0 = 0;						\
1:	r0 += 1;					\
	r1 = *(u64 *)(r10 - 8);				\
	if r0 & 0x80 goto 2f;				\
	if r0 < r1 goto 1b;				\
2:	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 3, header_count is 8")
__msg("loop header at 3, widening r0 to 2..9 step 1")
__msg("3: R0=scalar(smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=9,{{.*}})")
__msg("processed 6 insns")
__naked void post_cond_jlt_with_base(void)
{
	asm volatile ("					\
	r7 = 10 ll;	/* ldimm64 for a twist */	\
	r0 = 2;						\
1:	r0 += 1;					\
	if r0 < r7 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 1, header_count is 4 ")
__naked void latch_base_differs_from_step(void)
{
	asm volatile ("					\
	r0 = 0;						\
1:	r1 = r0;					\
	r1 += 1;					\
	if r1 >= 10 goto 2f;				\
	r0 += 4;					\
	goto 1b;					\
2:	r0 = r1;					\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 1, header_count is 11")
__msg("loop header at 1, widening r0 to 0..10 step 1")
__msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=10,{{.*}})")
__msg("processed 5 insns")
__naked void post_cond_jle(void)
{
	asm volatile ("					\
	r0 = 0;						\
1:	r0 += 1;					\
	if r0 <= 10 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 1, header_count is 10")
__msg("loop header at 1, widening r0 to 0..9 step 1")
__msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=9,{{.*}})")
__msg("processed 6 insns")
__naked void post_cond_jge(void)
{
	asm volatile ("					\
	r0 = 0;						\
1:	r0 += 1;					\
	if r0 >= 10 goto 2f;				\
	goto 1b;					\
2:	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 1, header_count is 11")
__msg("loop header at 1, widening r0 to 0..10 step 1")
__msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=10,{{.*}})")
__msg("processed 6 insns")
__naked void pre_cond_jge(void)
{
	asm volatile ("					\
	r0 = 0;						\
1:	if r0 >= 10 goto 2f;				\
	r0 += 1;					\
	goto 1b;					\
2:	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg_next("scev at header 1:")
__msg_next("  r0=(+ r0 1) / (linear r0 1)")
__msg_next(" scev at latch 2:")
__msg_next("  r0=(+ r0 1) / (linear (+ r0 1) 1)")
__msg("loop header at 1, widening r0")
__msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=2,{{.*}})")
__msg("1: (07) r0 += 1                       ; R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,{{.*}})")
__msg("2: (55) if r0 != 0x3 goto pc-2")
__msg("3: (95) exit")
__msg("loop header at 1, clamping r0")
__msg("from 2 to 1: safe")
__msg("processed 5 insns")
__naked void post_cond_jne(void)
{
	asm volatile ("					\
	r0 = 0;						\
1:	r0 += 1;					\
	if r0 != 3 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg_next("scev at header 1:")
__msg_next("  r0=(+ r0 -1) / (linear r0 -1)")
__msg_next(" scev at latch 2:")
__msg_next("  r0=(+ r0 -1) / (linear (+ r0 -1) -1)")
__msg("loop header at 1, header_count is 3 ")
__msg("loop header at 1, widening r0 to 1..3 step 1")
__msg("1: R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,var_off=(0x0; 0x3)) loop_stack=1")
__msg("loop header at 1, clamping r0 to 1..3 step 1")
__msg("processed 5 insns")
__naked void post_cond_jne_neg_step(void)
{
	asm volatile ("					\
	r0 = 3;						\
1:	r0 += -1;					\
	if r0 != 0 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

/*
 * r1 and r3 are widened independently, so the r3 == 5 path reaches the back
 * edge with r3 past the last value it takes at the header.
 */
SEC("socket")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 2, header_count is 5 ")
__msg("loop header at 2, widening r1 to 0..4 step 1")
__msg("loop header at 2, widening r3 to 0..4 step 1")
__msg("3: (55) if r3 != 0x5 goto pc+1 {{.*}}; R3=5")
__msg("loop header at 2, clamping r3 to 0..4 step 1")
__msg("from 6 to 2: safe")
__naked void clamp_dependent_overshoot(void)
{
	asm volatile ("					\
	r1 = 0;						\
	r3 = 0;						\
1:	r3 += 1;					\
	if r3 != 5 goto 2f;				\
	r2 = 0;						\
2:	r1 += 1;					\
	if r1 != 5 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/* Same with a 32-bit dependent register, SCEV (zext32 (linear r3 1)) */
SEC("socket")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 2, header_count is 5 ")
__msg("loop header at 2, widening r1 to 0..4 step 1")
__msg("loop header at 2, widening r3 to 0..4 step 1")
__msg("3: (56) if w3 != 0x5 goto pc+1 {{.*}}; R3=5")
__msg("loop header at 2, clamping r3 to 0..4 step 1")
__msg("from 6 to 2: safe")
__naked void clamp_dependent_overshoot32(void)
{
	asm volatile ("					\
	r1 = 0;						\
	w3 = 0;						\
1:	w3 += 1;					\
	if w3 != 5 goto 2f;				\
	r2 = 0;						\
2:	r1 += 1;					\
	if r1 != 5 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg_next("scev at header 1:")
__msg_next("  r0=(+ r0 1) / (linear r0 1)")
__msg_next(" scev at latch 1:")
__msg_next("  r0=(+ r0 1) / (linear r0 1)")
__msg("loop header at 1, widening r0")
__msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=3,{{.*}})")
__msg("1: (15) if r0 == 0x3 goto pc+2        ; R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=2,{{.*}})")
__msg("2: (07) r0 += 1                       ; R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,{{.*}})")
__msg("3: (05) goto pc-3")
__msg("loop header at 1, clamping r0")
__msg("1: safe")
__msg("from 1 to 4: R0=3")
__msg("4: R0=3")
__msg("4: (95) exit")
__msg("processed 6 insns")
__naked void pre_cond_je1(void)
{
	asm volatile ("					\
	r0 = 0;						\
1:	if r0 == 3 goto 2f;				\
	r0 += 1;					\
	goto 1b;					\
2:	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg_next("scev at header 1:")
__msg_next("  r0=(zext32 (+ r0 1)) / (zext32 (linear r0 1))")
__msg_next(" scev at latch 2:")
__msg_next("  r0=(zext32 (+ r0 1)) / (zext32 (linear (+ r0 1) 1))")
__msg("loop header at 1, widening r0")
__msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=2,{{.*}})")
__msg("1: (04) w0 += 1                       ; R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,{{.*}})")
__msg("2: (56) if w0 != 0x3 goto pc-2")
__msg("3: (95) exit")
__msg("loop header at 1, clamping r0")
__msg("from 2 to 1: safe")
__msg("processed 5 insns")
__naked void post_cond_jne32(void)
{
	asm volatile ("					\
	w0 = 0;						\
1:	w0 += 1;					\
	if w0 != 3 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

/* w0 ∈ {0xffffffff, 2, 5}, w0 % 3 ∈ {0, 2, 2} ⇒ step 3 can't be preserved */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("scev at header 1:")
__msg_next("  r0=(zext32 (+ r0 3)) / (zext32 (linear r0 3))")
__msg_next(" scev at latch 2:")
__msg_next("  r0=(zext32 (+ r0 3)) / (zext32 (linear (+ r0 3) 3))")
__msg("entering loop 1")
__msg_next("loop header at 1, header_count is 2")
__msg("loop header at 1, widening r0 to 0..0xffffffff (s32 -1..2) step 1")
__msg("1: R0=scalar(smin=0,smax=umax=0xffffffff,smin32=-1,smax32=2,{{.*}})")
__naked void post_cond_jne32_overflow(void)
{
	asm volatile ("					\
	w0 = 0xffffffff;				\
1:	w0 += 3;					\
	if w0 != 5 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

/*
 * w0 ∈ {0, 3, ..., 0xffffffff, 2, 5}, w0 % 3 ∈ {0, 0, ..., 0, 2, 2}
 * ⇒ step 3 can't be preserved.
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 2, header_count is 1431655767")
__msg("loop header at 2, widening r0 to 0..0xffffffff step 1")
__naked void post_cond_jne32_full_range(void)
{
	asm volatile ("					\
	w0 = 0;						\
	w1 = 0;						\
1:	w0 += 3;					\
	w1 += 1;					\
	if w1 != 1431655767 goto 1b;			\
	exit;						\
"	::: __clobber_all);
}

/* r0 ∈ {-6, 0xfffffff7, 0xfffffff4}, r0 % 3 ∈ {0, 1, 1} ⇒ step 3 can't be preserved. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 1, header_count is 2")
__msg("loop header at 1, widening r0 to -6..0xfffffffa (s32 -9..-6) step 1")
__naked void post_cond_jne32_base_mismatch(void)
{
	asm volatile ("					\
	r0 = -6;					\
1:	w0 += -3;					\
	if w0 != -12 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

/*
 * r0 ∈ {0, 0xffffffff, 0xfffffffe},
 * ⇒ the 64-bit header bounds are [0, U32_MAX], 32-bit header bounds are [-1, 0].
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 1, header_count is 2")
__msg("loop header at 1, widening r0 to 0..0xffffffff (s32 -1..0) step 1")
__naked void post_cond_jne32_neg_step(void)
{
	asm volatile ("					\
	w0 = 0;						\
1:	w0 += -1;					\
	if w0 != -2 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

/*
 * r0 ∈ {S64_MIN + 1, 3, 5}, r0 % 2 ∈ {1, 1, 1}
 * ⇒ step 2 and base 1 can be preserved.
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 2, header_count is 2")
__msg("loop header at 2, widening r0 to 0x8000000000000000..0x7fffffffffffffff (s32 1..3) step 2")
__msg("2: R0=scalar({{.*}}step=1+2)")
__naked void post_cond_jne32_signed_boundary(void)
{
	asm volatile ("					\
	r0 = %[initial] ll;				\
1:	w0 += 2;					\
	if w0 != 5 goto 1b;				\
	exit;						\
"	:
	: __imm_const(initial, ITER_S64_MIN + 1)
	: __clobber_all);
}

/* The pre-condition also visits the header with the terminating value 3. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 1, header_count is 4")
__msg("loop header at 1, widening r0 to 0..3 step 1")
__msg("loop header at 1, clamping r0")
__msg("4: R0=3")
__naked void pre_cond_je32(void)
{
	asm volatile ("					\
	w0 = 0;						\
1:	if w0 == 3 goto 2f;				\
	w0 += 1;					\
	goto 1b;					\
2:	exit;						\
"	::: __clobber_all);
}

/* ALU32 keeps r0 in [0, U32_MAX], so the 64-bit comparison never becomes false. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 4, can't compute iterations count")
__naked void post_cond_alu32_jmp64(void)
{
	asm volatile ("					\
	w0 = 0;						\
	r1 = 0x100000003 ll;				\
	r9 = 0;						\
1:	"
	LIMIT_ITERATIONS
	"w0 += 1;					\
	if r0 != r1 goto 1b;				\
2:	exit;						\
"	::: __clobber_all);
}

/* The signed 32-bit comparison is always true, even when r0 exceeds INT32_MAX. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 2, can't compute iterations count")
__naked void post_cond_alu64_jmp32(void)
{
	asm volatile ("					\
	r0 = %[initial];				\
	r9 = 0;						\
1:	"
	LIMIT_ITERATIONS
	"r0 += 1;					\
	if w0 s<= %[bound] goto 1b;			\
2:	exit;						\
"	:
	: __imm_const(initial, INT32_MAX - 1),
	  __imm_const(bound, INT32_MAX)
	: __clobber_all);
}

/* ALU32 values above INT32_MAX remain positive in a signed 64-bit comparison. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 3, header_count is 3")
__msg("loop header at 3, widening r0 to 0xfffffffc..0xfffffffe (s32 -4..-2) step 1")
__naked void post_cond_alu32_jmp64_bounded(void)
{
	asm volatile ("					\
	w0 = -4;					\
	r1 = 0xffffffff ll;				\
1:	w0 += 1;					\
	if r0 s< r1 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

/* The negative 64-bit counter and its exit value fit in the signed 32-bit range. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 1, header_count is 3")
__msg("loop header at 1, widening r0 to -6..-2 step 2")
__naked void post_cond_alu64_jmp32_bounded(void)
{
	asm volatile ("					\
	r0 = -6;					\
1:	r0 += 2;					\
	if w0 s< 0 goto 1b;				\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 1, header_count is [0..3] ")
__naked void one_backedge_two_exits(void)
{
	asm volatile ("					\
	r6 = 0;						\
1:	call %[bpf_get_prandom_u32];			\
	if r0 == 0 goto 2f;				\
	r6 += 1;					\
	if r6 != 3 goto 1b;				\
2:	r0 = r6;					\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg_next("scev at header 11:")
__msg_next("  r0=(+ r0 1) / (linear r0 1)")
__msg_next("  r1=(+ r1 2) / (linear r1 2)")
__msg_next(" scev at latch 16:")
__msg_next("  r0=(+ r0 1) / (linear (+ r0 1) 1)")
__msg_next("  r1=(+ r1 2) / (linear (+ r1 2) 2)")
__msg("loop header at 11, widening r0")
__msg("loop header at 11, widening r1")
__msg("11: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=7,var_off=(0x0; 0x7)) R1=scalar(smin=smin32=0,smax=umax=smax32=umax32=14,var_off=(0x0; 0xe),step=0+2)")
/* loop exit */
__msg("16: (a5) if r0 < 0x8 goto pc-6")
__msg("exiting loop 11")
__msg("17: (95) exit")
/* second iteration */
__msg("loop header at 11, clamping r0")
__msg("loop header at 11, clamping r1")
/* iteration convergence */
__msg("from 16 to 11: safe")
__not_msg("{{^}}11:")
/* map lookup error path */
__msg("from 7 to 17: safe")
__naked void correlated_regs(void)
{
	asm volatile ("					\
	r1 = 0;						\
	*(u64*)(r10 - 8) = r1;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[map] ll;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r6 = r0;					\
	r0 = 0;						\
	r1 = 0;						\
1:	r2 = r6;					\
	r2 += r1;					\
	*(u8 *)(r2 + 0) = 1;				\
	r0 += 1;					\
	r1 += 2;					\
	if r0 < 8 goto 1b;				\
2:	exit;						\
"	:
	: __imm(bpf_map_lookup_elem),
	  __imm_addr(map)
	: __clobber_all);
}

/*
 * k = 0
 * for (i = 0; i < 4; i++):
 *   for (j = 0; j < 4; j++):
 *     k += 1
 *     k <<= 1   // make SCEV construction not possible
 *     k >>= 1
 * map[k] = 1    // make k precise
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("19: (72) *(u8 *)(r4 +0) = 1           ; R4=map_value(id={{.*}},map=map,ks=4,vs=1024,imm=16)")
__not_msg("19: ")
__msg("processed 106 insns")
__naked void nested_loops_precise_var1(void)
{
	asm volatile ("					\
	*(u64*)(r10 - 8) = 0;				\
	r1 = %[map] ll;					\
	r2 = r10;					\
	r2 += -8;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 3f;				\
	r1 = 0;						\
	r3 = 0;						\
	/* outer loop */				\
1:	r2 = 0;						\
	/* inner loop */				\
2:	r2 += 1;					\
	r3 += 1;					\
	r3 <<= 1;					\
	r3 >>= 1;					\
	if r2 < 4 goto 2b;				\
	r1 += 1;					\
	if r1 < 4 goto 1b;				\
	r4 = r0;					\
	r4 += r3;					\
	*(u8 *)(r4 + 0) = 1;				\
	r0 = 0;						\
3:	exit;						\
"	:
	: __imm(bpf_map_lookup_elem),
	  __imm_addr(map)
	: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__msg("loop header at 2, header_count is 100 ")
__msg("loop header at 4, header_count is [0..100] ")
__msg("loop header at 6, header_count is [0..100] ")
__msg("processed 20 insns")
__flag(BPF_F_TEST_STATE_FREQ)
__naked void nested_loop_with_two_exits(void)
{
	asm volatile ("					\
	call %[bpf_get_prandom_u32];			\
	r6 = 0;						\
1:	r6 += 1;					\
	r7 = 0;						\
2:	r7 += 1;					\
	r8 = 0;						\
3:	r8 += 1;					\
	call %[bpf_get_prandom_u32];			\
	if r0 == 42 goto +1;				\
	goto 4f;					\
	if r8 < 100 goto 3b;				\
	if r7 < 100 goto 2b;				\
4:	if r6 < 100 goto 1b;				\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__naked void exit_loop_into_loop_header(void)
{
	asm volatile ("					\
	r1 = 0;						\
	r2 = 0;						\
loop_a_%=:						\
	r1 += 1;					\
	if r1 < 10 goto loop_a_%=;			\
loop_b_%=:						\
	r2 += 1;					\
	if r2 < 10 goto loop_b_%=;			\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/*
 * This exercises verifier.c:loop_stack_{pop,push}() implementation,
 * at 'goto d' loops 'b' and 'a' have to be popped from stack,
 * while loops 'c' and 'd' have to be pushed to stack.
 *
 *   loop a:                  // header 5
 *     loop b:                // header 6
 *       if (rand) goto d;    // 8 -> 12, side entry into inner loop d
 *       ...
 *   loop c:                  // header 11
 *     loop d:                // header 12
 *       ...
 */
SEC("xdp")
__log_level(2)
__msg("loop at 5")
__msg("loop at 6, nested in 5")
__msg("loop at 11, irreducible")
__msg("loop at 12, nested in 11")
/* entry via if r0 == 5 goto d_%= false branch */
__msg("loop header at 12, header_count is 3 ")
__msg("loop header at 12, widening r9 to 0..2 step 1")
__msg("12: R8=1 R9=scalar(smin=smin32=0,smax=umax=smax32=umax32=2,var_off=(0x0; 0x3)) loop_stack=11,12")
/* entry via if r0 == 5 goto d_%= true branch */
__msg("loop header at 12, header_count is 3 ")
__msg("loop header at 12, widening r9 to 0..2 step 1")
__msg("from 8 to 12: R8=0 R9=scalar(smin=smin32=0,smax=umax=smax32=umax32=2,var_off=(0x0; 0x3)) R10=fp0 loop_stack=11,12")
__naked void enter_nested_loop_from_side(void)
{
	asm volatile ("					\
	call %[bpf_get_prandom_u32];			\
	r6 = 0;						\
	r7 = 0;						\
	r8 = 0;						\
	r9 = 0;						\
a_%=:	r6 += 1;					\
b_%=:	r7 += 1;					\
	call %[bpf_get_prandom_u32];			\
	if r0 == 5 goto d_%=;				\
	if r7 < 3 goto b_%=;				\
	if r6 < 3 goto a_%=;				\
c_%=:	r8 += 1;					\
d_%=:	r9 += 1;					\
	if r9 < 3 goto d_%=;				\
	if r8 < 3 goto c_%=;				\
	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * Loop A (counter in r6) contains irreducible loop B (header 5),
 * which contains C (counter in r9).
 * Entering B at 'body' saves and restores r6, making it appear invariant.
 * Entering B at 'alternate' skips the save and modifies r6 instead.
 * Hence A must not infer a SCEV expression for r6.
 * SCEV expression for r9 in C should still be computed.
 *
 *  0: r6 = 0;
 *     do {                              // A
 *  1:     r6++;
 *  2:     r0 = bpf_get_prandom_u32();
 *  3:     r7 = 0;
 *  4:     if (r0 > 5) goto alternate;
 *  5: B:  r8 = r6;                      // B
 *  6:     goto body;
 *  7: alternate:
 *         r8 = r6;
 *  8:     r8++;
 *  9: body:
 *         r6 = r8;
 * 10:     r9 = 0;
 *         do {                          // C
 * 11:         r9++;
 * 12:     } while (r9 < 3);
 * 13:     r7++;
 * 14:     if (r7 < 4) goto B;
 * 15: } while (r6 < 4);
 * 16: r0 = 0;
 * 17: return r0;
 */
SEC("xdp")
__success
__log_level(2)
__msg("loop at 1{{$}}")
__msg("loop at 5, nested in 1, irreducible")
__msg("loop at 11, nested in 5")
__msg("scev at header 1:")
__msg_next("  r6=?")
__msg("scev at header 11:")
__msg_next("  r9=(+ r9 1) / (linear r9 1)")
__msg("loop header at 11, widening r9 to 0..2 step 1")
__not_msg("loop header at 1, widening r6")
__naked void nested_irreducible_loop(void)
{
	asm volatile ("					\
	r6 = 0;						\
a_%=:	r6 += 1;					\
	call %[bpf_get_prandom_u32];			\
	r7 = 0;						\
	if r0 > 5 goto alternate_%=;			\
b_%=:	r8 = r6;					\
	goto body_%=;					\
alternate_%=:						\
	r8 = r6;					\
	r8 += 1;					\
body_%=:						\
	r6 = r8;					\
	r9 = 0;						\
c_%=:	r9 += 1;					\
	if r9 < 3 goto c_%=;				\
	r7 += 1;					\
	if r7 < 4 goto b_%=;				\
	if r6 < 4 goto a_%=;				\
	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * Loop A (counter in r6) contains irreducible loop B.
 * Loop B has an exit edge from A. This is a corner case
 * observed during testing: insn_aux_data[l1].need_scev == true,
 * but SCEV environment is not constructed.
 *
 *	  r6 = 0;
 *	  do {					// A
 *	     r6++;
 *	     r0 = bpf_get_prandom_u32();
 *	     r7 = 0;
 *	     if (r0 > 5) goto alternate;
 *	     do {				// B
 *	       r7++;
 * alt:	       r0 = bpf_get_prandom_u32();
 * l1:	       if (r0 == 42)
 *		 goto exit;
 *	       r7++;
 *	     } while (r7 < 4);
 *	  } while (r6 < 4);
 *	  r0 = 0;
 * exit:  return r0;
 */
SEC("xdp")
__success
__log_level(2)
__naked void nested_irreducible_loop2(void)
{
	asm volatile ("					\
	r6 = 0;						\
a_%=:	r6 += 1;					\
	call %[bpf_get_prandom_u32];			\
	r7 = 0;						\
	if r0 > 5 goto alternate_%=;			\
b_%=:	r7 += 1;					\
alternate_%=:						\
	call %[bpf_get_prandom_u32];			\
	if r0 == 42 goto exit_%=;			\
	r7 += 1;					\
	if r7 < 4 goto b_%=;				\
	if r6 < 4 goto a_%=;				\
	r0 = 0;						\
exit_%=:exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * Induction variable seeded from a non-constant value. r7 enters the loop as a
 * range aligned to 2 (prandom & 0x6 -> {0,2,4,6}) and is incremented by a
 * non-power-of-2 slope of 6. Since the entry value is not a single point, only
 * the power-of-two alignment shared by the entry value and the slope can be
 * guaranteed, so the widened step is 2.
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 4, widening r7 to 0..18 step 2")
__msg("R7=scalar(smin=smin32=0,smax=umax=smax32=umax32=18,var_off=(0x0; 0x1e),step=0+2)")
__naked void widen_nonconst_base(void)
{
	asm volatile ("					\
	call %[bpf_get_prandom_u32];			\
	r7 = r0;					\
	r7 &= 0x6;					\
	r6 = 0;						\
1:	r7 += 6;					\
	r6 += 1;					\
	if r6 < 3 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * After excluding zero from {0,4,8,12}, the interval starts at 1 while the
 * values remain multiples of 4. Widening over three iterations must preserve
 * base 0 and include 20.
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 5, header_count is 3 ")
__msg("5: R7=scalar({{.*}}smax=umax=smax32=umax32=20,{{.*}}step=0+4)")
__naked void widen_nonconst_base_refined(void)
{
	asm volatile ("					\
	call %[bpf_get_prandom_u32];			\
	r7 = r0;					\
	r7 &= 0xc;					\
	if r7 < 1 goto 2f;				\
	r8 = 0;						\
1:	r7 += 4;					\
	r8 += 1;					\
	if r8 < 3 goto 1b;				\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * Two nested loops with (1) exiting directly to (2):
 *
 *   for (r6 = 0; r6 < 4; r6++) {
 *     r7 = 0;
 *     for (; r7 <  3; r7++) {}   // (1)
 *     for (; r7 != 0; r7--) {}   // (2)
 *   }
 */
SEC("xdp")
__success
__log_level(2)
__msg("loop header at 1, widening r6 to 0..3 step 1")
__msg("loop header at 2, widening r7 to 0..2 step 1")
__msg("exiting loop 2")
__msg("entering loop 4")
__msg("loop header at 4, widening r7 to 1..3 step 1")
__naked void sibling_inner_loops(void)
{
	asm volatile ("					\
	r6 = 0;						\
1:	r7 = 0;						\
2:	r7 += 1;					\
	if r7 < 3 goto 2b;				\
3:	r7 += -1;					\
	if r7 != 0 goto 3b;				\
	r6 += 1;					\
	if r6 < 4 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

SEC("socket")
__success
__log_level(2)
__msg("loop header at 0, can't compute iterations count")
__naked void uninit_slot_counter(void)
{
	asm volatile ("					\
1:	r0 = *(u64 *)(r10 - 8);				\
	r0 += 1;					\
	*(u64 *)(r10 - 8) = r0;				\
	if r0 < 10 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/*
 * The assignment happens only on the second iteration:
 *
 *   r7 = 5;
 *   for (r6 = 0; r6 < 3; r6++)
 *           if (r6 == 1)
 *                   r7 = 10;
 *   if (r7 != 10)
 *           invalid_stack_read();
 *
 * R7 is always 10 at the real exit. Widening loses the correlation between
 * R6 and R7, leaving R7 in [5, 10] both at the loop header and after the loop.
 * The verifier therefore rejects the possible invalid stack read.
 */
SEC("xdp")
__failure
__log_level(2)
__msg("2: {{.*}}R7=scalar(smin=umin=smin32=umin32=5,smax=umax=smax32=umax32=10,var_off=(0x0; 0xf))")
__msg("7: R7=scalar(smin=umin=smin32=umin32=5,smax=umax=smax32=umax32=10,var_off=(0x0; 0xf))")
__msg("invalid read from stack R10 off=0 size=8")
__naked void conditional_assignment_on_second_iteration(void)
{
	asm volatile ("					\
	r7 = 5;						\
	r6 = 0;						\
1:	if r6 >= 3 goto 3f;				\
	if r6 != 1 goto 2f;				\
	r7 = 10;					\
2:	r6 += 1;					\
	goto 1b;					\
3:	if r7 == 10 goto 4f;				\
	r0 = *(u64 *)(r10 + 0);				\
4:	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/*
 * The latch bound has header SCEV (any r7 100), so it is not invariant:
 *
 *   u64 i = 0, n = 3;
 *   for (;;) {
 *           ++i;
 *           if (i >= n)
 *                   break;
 *           if (i == 1)
 *                   n = 100;
 *   }
 *
 * The ANY expression must also appear at the latch, rather than a bare r7
 * that would incorrectly be treated as a loop-invariant bound.
 */
SEC("xdp")
__success
__log_level(2)
__msg("scev at header 2:")
__msg_next("  r6=(+ r6 1) / (linear r6 1)")
__msg_next("  r7=(any r7 100) / (any r7 100)")
__msg_next(" scev at latch 3:")
__msg_next("  r6=(+ r6 1) / (linear (+ r6 1) 1)")
__msg_next("  r7=r7 / (any r7 100)")
__naked void no_widen_changing_latch_bound(void)
{
	asm volatile ("					\
	r6 = 0;						\
	r7 = 3;						\
loop_%=:						\
	r6 += 1;					\
	if r6 >= r7 goto exit_%=;			\
	if r6 != 1 goto next_%=;			\
	r7 = 100;					\
next_%=:						\
	goto loop_%=;					\
exit_%=:						\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/*
 * Join two stack pointer offsets via (any r7 r8), with r8 loop-invariant.
 * The joined range [-16, -8] still points to initialized stack memory,
 * so dereferencing r7 after the loop is safe.
 */
SEC("xdp")
__success __retval(0)
__log_level(2)
__msg("loop header at 7, widening r7 to -16..-8 step 1")
__msg("7: {{.*}}R7=fp(smin=smin32=-16,smax=smax32=-8,")
__msg("12: R7=fp(smin=smin32=-16,smax=smax32=-8,")
__naked void conditional_stack_pointer_assignment(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 16) = 0;				\
	*(u64 *)(r10 - 8) = 0;				\
	r7 = r10;					\
	r7 += -16;					\
	r8 = r10;					\
	r8 += -8;					\
	r6 = 0;						\
1:	if r6 >= 3 goto 3f;				\
	if r6 != 1 goto 2f;				\
	r7 = r8;					\
2:	r6 += 1;					\
	goto 1b;					\
3:	r0 = *(u64 *)(r7 + 0);				\
	exit;						\
"	::: __clobber_all);
}

/*
 * Both choices are valid, but combining their offsets while retaining
 * small_map's metadata would invent small_map + 32, outside its value.
 *
 *   r6 = lookup(small_map, 0);
 *   r7 = lookup(map, 0) + 32;
 *   for (r8 = 0; r8 < 3; r8++) {
 *           if (r8 == 1)
 *                   r6 = r7;
 *           r0 = *(u32 *)(r6 + 0);
 *   }
 */
SEC("xdp")
__success __retval(0)
__log_level(2)
__msg("loop header at {{[0-9]+}}, can't widen r6, expr is")
__not_msg("widening")
__naked void no_widen_any_map_origin(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[small_map] ll;				\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 3f;				\
	r6 = r0;					\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[map] ll;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 3f;				\
	r7 = r0;					\
	r7 += 32;					\
	r8 = 0;						\
1:	if r8 != 1 goto 2f;				\
	r6 = r7;					\
2:	r0 = *(u32 *)(r6 + 0);				\
	r8 += 1;					\
	if r8 < 3 goto 1b;				\
3:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem), __imm_addr(small_map), __imm_addr(map)
	: __clobber_all);
}

__naked __noinline __used static int any_stack_origin_callee(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r6 = r1;					\
	r7 = r10;					\
	r7 += -8;					\
	r8 = 0;						\
1:	if r8 != 1 goto 2f;				\
	r6 = r7;					\
2:	r8 += 1;					\
	if r8 < 3 goto 1b;				\
	r0 = *(u64 *)(r6 + 0);				\
	exit;						\
"	::: __clobber_all);
}

/*
 * The callee chooses between caller fp-16 and its own fp-8:
 *
 *   r6 = r1;
 *   r7 = fp - 8;
 *   for (r8 = 0; r8 < 3; r8++)
 *           if (r8 == 1)
 *                   r6 = r7;
 *   return *(u64 *)r6;
 *
 * Both locations hold zero. Their offsets belong to different frames
 * and cannot be combined into one stack pointer.
 */
SEC("xdp")
__success __retval(0)
__log_level(2)
__msg("loop header at {{[0-9]+}}, can't widen r6, expr is")
__not_msg("widening")
__naked void no_widen_any_stack_origin(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 16) = 0;				\
	r1 = r10;					\
	r1 += -16;					\
	call any_stack_origin_callee;			\
	exit;						\
"	::: __clobber_all);
}

__naked __noinline __used static int scrub_slot_callee(void)
{
	asm volatile ("					\
	*(u32 *)(r1 + 4) = 1;				\
	call %[bpf_get_prandom_u32];			\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * The callee turns the caller's fp-8 into misc, so the states at the call site
 * differ between the first and the second iteration, while the states inside
 * the callee are identical. Verification fails with an infinite loop error if
 * states.c:current_loop() does not search upper frames for active loops.
 */
SEC("socket")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 3, widening r6 to 0..9 step 1")
__msg("loop header at 3, clamping r6 to 0..9 step 1")
__msg("12: safe")
__naked void clamp_callee_state_pruning(void)
{
	asm volatile ("					\
	w1 = 1;						\
	*(u32 *)(r10 - 8) = r1;				\
	r6 = 0;						\
1:	r1 = r10;					\
	r1 += -8;					\
	call scrub_slot_callee;				\
	r6 += 1;					\
	if r6 < 10 goto 1b;				\
	r0 = *(u32 *)(r10 - 8);				\
	exit;						\
"	::: __clobber_all);
}

/*
 * The inner loop turns fp-8 from a spill into misc. On the next outer
 * iteration, the states inside the inner loop match its first invocation.
 */
SEC("socket")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 3, widening r6 to 0..9 step 1")
__msg("loop header at 4, widening r7 to 0..2 step 1")
__msg("loop header at 3, clamping r6 to 0..9 step 1")
__naked void clamp_nested_loop_state_pruning(void)
{
	asm volatile ("					\
	w1 = 1;						\
	*(u32 *)(r10 - 8) = r1;				\
	r6 = 0;						\
1:	r7 = 0;						\
2:	*(u32 *)(r10 - 4) = 1;				\
	r7 += 1;					\
	if r7 < 3 goto 2b;				\
	r6 += 1;					\
	if r6 < 10 goto 1b;				\
	r0 = *(u32 *)(r10 - 8);				\
	exit;						\
"	::: __clobber_all);
}

/*
 * Same as above, but the inner loop is not recognized by SCEV and is unrolled
 * with a precise r7. The states at its header still match between the outer
 * iterations and must not be reported as an infinite loop: the path between
 * them crosses the back edge of the terminating outer loop.
 */
SEC("socket")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 3, widening r6 to 0..9 step 1")
__msg("loop header at 5, can't compute iterations count")
__msg("loop header at 3, clamping r6 to 0..9 step 1")
__naked void clamp_nested_unrolled_loop_state_pruning(void)
{
	asm volatile ("					\
	w1 = 1;						\
	*(u32 *)(r10 - 8) = r1;				\
	r6 = 0;						\
1:	*(u32 *)(r10 - 4) = 1;				\
	r7 = 1;						\
2:	r7 *= 2;					\
	if r7 < 4 goto 2b;				\
	r6 += 1;					\
	if r6 < 10 goto 1b;				\
	r0 = *(u32 *)(r10 - 8);				\
	exit;						\
"	::: __clobber_all);
}

/*
 * r7 starts as 1 + 6*k and invariant r8 as 1 + 9*k (0 <= k <= 3).
 * The (any r7 r8) union must preserve base 1 and step gcd(6, 9) = 3.
 */
SEC("xdp")
__success __retval(1)
__log_level(2)
__msg("r7 += 1 {{.*}}step=1+6)")
__msg("r8 += 1 {{.*}}step=1+9)")
__msg("loop header at 9, widening r7 to 1..28 step 3")
__msg("9: {{.*}}R7=scalar({{.*}},step=1+3)")
__msg("14: R7=scalar({{.*}},step=1+3)")
__naked void conditional_scalar_assignment_gcd(void)
{
	asm volatile ("					\
	call %[bpf_get_prandom_u32];			\
	r0 &= 3;					\
	r7 = r0;					\
	r7 *= 6;					\
	r7 += 1;					\
	r8 = r0;					\
	r8 *= 9;					\
	r8 += 1;					\
	r6 = 0;						\
1:	if r6 >= 3 goto 3f;				\
	if r6 != 1 goto 2f;				\
	r7 = r8;					\
2:	r6 += 1;					\
	goto 1b;					\
3:	r0 = r7;					\
	r0 %%= 3;					\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * r7 = ctx->data;
 * r8 = r7
 * for (r6 = 0; r6 < 10 && random() != 42; r7++, r6++);
 * if (r7 >= ctx->data_end)
 *   return;
 * *(r8 + 4);  // At this point the loop executed unknown number of times.
 *	       // Hence, r7 range gives no information about r8.
 */
SEC("tc")
__failure
__msg("R8 min value is outside of the allowed memory range")
__naked void break_pkt_pointers_id(void)
{
	asm volatile ("					\
	r7 = *(u32*)(r1 + %[__sk_buff_data]);		\
	r8 = r7;					\
	r9 = *(u32*)(r1 + %[__sk_buff_data_end]);	\
	r6 = 0;						\
1:	call %[bpf_get_prandom_u32];			\
	if r0 == 42 goto 3f;				\
	r6 += 1;					\
	r7 += 1;					\
	if r6 < 10 goto 1b;				\
3:	if r7 >= r9 goto 2f;				\
	r0 = *(u8*)(r8 + 4);				\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)),
	  __imm_const(__sk_buff_data_end, offsetof(struct __sk_buff, data_end)),
	  __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * A loop induction variable used to compute the base address of a store to the
 * stack must not be widened: the spill offset would become varying, which the
 * verifier does not track.
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 2, can't widen r2, expr is (+ r2 8), requires exact stack-offset tracking")
__naked void no_widen_stack_spill(void)
{
	asm volatile ("					\
	r0 = 0;						\
	r2 = 0;						\
1:	r3 = r10;					\
	r3 += -64;					\
	r3 += r2;					\
	*(u64 *)(r3 + 0) = r0;				\
	r0 += 1;					\
	r2 += 8;					\
	if r0 < 4 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}
/*
 * Same hazard across a loop nest: the outer induction variable r2 addresses a
 * stack store performed inside the inner loop. The dependency is pulled up from
 * the inner loop, so the outer loop must not widen r2.
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 2, can't widen r2, expr is (+ r2 8), requires exact stack-offset tracking")
__msg("loop header at 3, widening r1 to 0..1 step 1")
__naked void no_widen_stack_spill_nested(void)
{
	asm volatile ("					\
	r0 = 0;						\
	r2 = 0;						\
1:	r1 = 0;						\
2:	r3 = r10;					\
	r3 += -64;					\
	r3 += r2;					\
	*(u64 *)(r3 + 0) = r1;				\
	r1 += 1;					\
	if r1 < 2 goto 2b;				\
	r0 += 1;					\
	r2 += 8;					\
	if r0 < 4 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/*
 * The inner loop restores r6 on its backedge but exits with r6 = -1000 on break.
 * Outer loop must account for the exit value instead of deriving r6 = r6_entry + n.
 * On the first outer backedge r6 is -999, so the next map access is invalid.
 *
 *   u8 *r7 = map_value;
 *   s64 r6 = 0;
 *   do {
 *   1:       r9 = 0;
 *           r0 = r7[r6];
 *           while (true) {
 *   2:              r8 = r6;
 *                   r6 = -1000;
 *                   if (++r9 > 5)
 *                           break;
 *                   r6 = r8;
 *   3:      }
 *           r6++;
 *   } while (r6 < 3);
 */
SEC("xdp")
__failure
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("scev at header 9:")
__msg_next("  r6=(+ ? 1) / ?")
__msg_next(" scev at latch 20:")
__msg_next("  r6=(+ ? 1) / (+ ? 1)")
__msg_next("scev at header 13:")
__msg_next("  r9=(+ r9 1) / (linear r9 1)")
__msg_next(" scev at latch 16:")
__msg_next("  r6=-1000 / -1000")
__msg_next("  r8=r6 / r6")
__msg_next("  r9=(+ r9 1) / (linear (+ r9 1) 1)")
__msg("R6=-999")
__msg("R1 min value is negative")
__naked void nested_loop_exit_clobbers_reg(void)
{
	asm volatile (
	"*(u64 *)(r10 - 8) = 0;"
	"r2 = r10;"
	"r2 += -8;"
	"r1 = %[map] ll;"
	"call %[bpf_map_lookup_elem];"
	"if r0 == 0 goto 4f;"
	"r7 = r0;"
	"r6 = 0;"
"1:"
	"r9 = 0;"
	"r1 = r7;"
	"r1 += r6;"
	"r0 = *(u8 *)(r1 + 0);"
"2:"
	"r8 = r6;"
	"r6 = -1000;"
	"r9 += 1;"
	"if r9 > 5 goto 3f;"
	"r6 = r8;"
	"goto 2b;"
"3:"
	"r6 += 1;"
	"if r6 s< 3 goto 1b;"
"4:"
	"r0 = 0;"
	"exit;"
	:
	: __imm(bpf_map_lookup_elem),
	  __imm_addr(map)
	: __clobber_all);
}

/*
 * The inner loop exits both nested loops with r6 unchanged, or exits only itself with r6 = -1000.
 * The middle loop repairs the latter exit with a stack fill. It therefore preserves r6,
 * so the outermost loop must retain r6_entry + n.
 *
 *   r6 = 0;
 *   do {
 *           r7 = 0;
 *           do {
 *                   spill = r6;
 *                   r9 = 0;
 *                   do {
 *                           r8 = r6;
 *                           if (random() & 1)
 *                                   goto next;
 *                           r6 = -1000;
 *                           if (++r9 >= 2)
 *                                   break;
 *                           r6 = r8;
 *                   } while (true);
 *                   r6 = spill;
 *           } while (++r7 < 2);
 *   next:
 *           r6++;
 *   } while (r6 < 3);
 */
SEC("xdp")
__success __retval(3)
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("r6 = *(u64 *)(r10 -8) {{.*}}; r6 ? -> r6")
__msg("scev at header 1:")
__msg_next("  r6=(+ r6 1) / (linear r6 1)")
__msg_next(" scev at latch 16:")
__msg_next("  r6=(+ r6 1) / (linear (+ r6 1) 1)")
__msg("scev at header 2:")
__msg_next("  r7=(+ r7 1) / (linear r7 1)")
__msg("scev at header 4:")
__msg_next("  r9=(+ r9 1) / (linear r9 1)")
__msg(" scev at latch 9:")
__msg_next("  r8=r6 / r6")
__msg_next("  r9=(+ r9 1) / (linear (+ r9 1) 1)")
__naked void nested_loop_exit_preserves_reg(void)
{
	asm volatile (
	"r6 = 0;"
"1:"
	"r7 = 0;"
"2:"
	"*(u64 *)(r10 - 8) = r6;"
	"r9 = 0;"
"3:"
	"r8 = r6;"
	"call %[bpf_get_prandom_u32];"
	"if r0 & 1 goto 5f;"
	"r6 = -1000;"
	"r9 += 1;"
	"if r9 >= 2 goto 4f;"
	"r6 = r8;"
	"goto 3b;"
"4:"
	"r6 = *(u64 *)(r10 - 8);"
	"r7 += 1;"
	"if r7 < 2 goto 2b;"
"5:"
	"r6 += 1;"
	"if r6 < 3 goto 1b;"
	"r0 = r6;"
	"exit;"
	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * Complement of no_widen_stack_spill: a sub-register (1-byte) store to the stack
 * lands as STACK_MISC and carries no tracked value, so the induction variable
 * addressing it (r2) is still widened.
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("widening r2 to 0..24 step 8")
__naked void widen_byte_stack_store(void)
{
	asm volatile ("					\
	r0 = 0;						\
	r2 = 0;						\
1:	r3 = r10;					\
	r3 += -64;					\
	r3 += r2;					\
	*(u8 *)(r3 + 0) = r0;				\
	r0 += 1;					\
	r2 += 8;					\
	if r0 < 4 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/*
 * A fill (BPF_LDX) at a varying stack offset loses precision just like a spill,
 * so the induction variable computing the load base (r2) must not be widened.
 * The slots are initialized up front so the fill itself is a valid read.
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 6, can't widen r2, expr is (+ r2 8), requires exact stack-offset tracking")
__naked void no_widen_stack_fill(void)
{
	asm volatile ("					\
	r0 = 0;						\
	*(u64 *)(r10 - 64) = r0;			\
	*(u64 *)(r10 - 56) = r0;			\
	*(u64 *)(r10 - 48) = r0;			\
	*(u64 *)(r10 - 40) = r0;			\
	r2 = 0;						\
1:	r3 = r10;					\
	r3 += -64;					\
	r3 += r2;					\
	r4 = *(u64 *)(r3 + 0);				\
	r0 += 1;					\
	r2 += 8;					\
	if r0 < 4 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/*
 * struct xdp_md *slots[2] = { ctx, ctx };
 *
 * r7 = 0;
 * for (r8 = 0; r8 < 2; r8++) {
 *         value = slots[r7]->data;
 *         if (i == 0)
 *                 r7 = 1;
 * }
 *
 * SCEV expression for r7 is (any r7 8) and r7 is used to
 * address the stack memory. Avoid widening it, otherwise
 * verifier won't know the type of the slots[r7] expression.
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("scev at header 4:")
__msg_next("r7=(any r7 8) / (any r7 8)")
__msg("loop header at 4, can't widen r7, expr is {{.*}}, requires exact stack-offset tracking")
__naked void no_widen_stack_fill_any(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 16) = r1;			\
	*(u64 *)(r10 - 8) = r1;				\
	r7 = 0;						\
	r8 = 0;						\
1:	r2 = r10;					\
	r2 += -16;					\
	r2 += r7;					\
	r3 = *(u64 *)(r2 + 0);	/* slots[r7] */		\
	r0 = *(u32 *)(r3 + 0);	/* slots[r7]->data */	\
	if r8 != 0 goto 2f;				\
	r7 = 8;			/* conditionally update r7 */ \
2:	r8 += 1;					\
	if r8 < 2 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/*
 * A dynptr/iter/irq/res_spin_lock call initializes a stack object through a
 * pointer argument, which acts like a spill base: the induction variable
 * computing that argument's varying stack offset must not be widened, otherwise
 * the slot can't be resolved. Here each iteration constructs an xdp dynptr at
 * &dptrs[i].
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("can't widen {{.*}}, requires exact stack-offset tracking")
#ifndef __clang__
/* The issue is unrelated to SCEV */
__skip("GCC emits a stack-pointer loop condition the verifier cannot resolve")
#endif
int no_widen_dynptr_kfunc_arg(struct xdp_md *ctx)
{
	struct bpf_dynptr dptrs[4];
	int i;

#ifdef __clang__
#pragma clang loop unroll(disable)
#else
#pragma GCC unroll 0
#endif
	for (i = 0; i < 4; i++)
		bpf_dynptr_from_xdp(ctx, 0, &dptrs[i]);

	return 0;
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("header_count is 4 ")
__msg("widening r6 to -16..-13 step 1")
__naked void ptr_stack(void)
{
	asm volatile ("					\
	r6 = r10;					\
	r6 += -16;					\
	r7 = r6;					\
	r7 += 4;					\
1:	r6 += 1;					\
	if r6 < r7 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

__naked __noinline __used static int ptr_stack_callee(void)
{
	asm volatile ("					\
	r6 = r10;					\
	r6 += -16;					\
	r7 = r1;					\
	r0 = 0;						\
1:	r6 += 1;					\
	r0 += 1;					\
	if r0 & 8 goto 4f;	/* bound main pass iteration, but hide it from SCEV */	\
	if r6 < r7 goto 1b;	/* r6 and r7 are from different frames, can't be widened */	\
4:	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/* The end pointer belongs to the caller's frame. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("scev: incompatible latch operands r6 (fp), r7 (fp)")
__not_msg("widening r6")
__naked void ptr_stack_other_frame(void)
{
	asm volatile ("					\
	r1 = r10;					\
	r1 += -12;					\
	call ptr_stack_callee;				\
	exit;						\
"	::: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__msg("scev: incompatible latch operands r6 (map_value), r7 (map_value)")
__msg("loop header at 11, can't compute iterations count at 14")
__naked void ptr_map_value_jmp32(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[map] ll;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r6 = r0;					\
	r7 = r6;					\
	r7 += 4;					\
	r9 = 0;						\
1:"	LIMIT_ITERATIONS				\
"	r6 += 1;					\
	if w6 < w7 goto 1b;				\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem), __imm_addr(map)
	: __clobber_all);
}

SEC("xdp")
__failure
__log_level(2)
__msg("loop header at 11, can't compute iterations count")
__msg("R6 32-bit pointer arithmetic prohibited")
__naked void ptr_map_value_alu32_latch(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[map] ll;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r6 = r0;					\
	r7 = r6;					\
	r7 += 4;					\
	r9 = 0;						\
1:"	LIMIT_ITERATIONS				\
"	w6 += 1;					\
	if r6 < r7 goto 1b;				\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem), __imm_addr(map)
	: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__msg("loop header at 11, can't compute iterations count")
__naked void ptr_map_value_alu32_latch2(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[map] ll;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r6 = r0;					\
	r7 = r6;					\
	r7 += 4;					\
	r9 = 0;						\
1:"	LIMIT_ITERATIONS				\
"	r6 += 1;					\
	w8 = w6;					\
	if r8 < r7 goto 1b;				\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem), __imm_addr(map)
	: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__msg("loop header at 8, can't widen r0, expr is (zext32 (+ r0 1))")
__naked void ptr_map_value_alu32_non_latch(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[map] ll;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r1 = 0;						\
1:	r1 += 1;					\
	w0 = w0;					\
	w0 += 1;					\
	if r1 < 4 goto 1b;				\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem), __imm_addr(map)
	: __clobber_all);
}

/* Metadata and packet data have different origins. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("scev: incompatible latch operands r6 (pkt_meta), r7 (pkt)")
__not_msg("widening r6")
__naked void ptr_packet_meta_other_origin(void)
{
	asm volatile ("					\
	r6 = *(u32 *)(r1 + %[data_meta]);		\
	r7 = *(u32 *)(r1 + %[data]);			\
	r7 += 4;					\
	r0 = 0;						\
1:	r6 += 1;					\
	r0 += 1;					\
	if r0 & 8 goto 4f;				\
	if r6 < r7 goto 1b;				\
4:	r0 = 0;						\
	exit;						\
"	:
	: __imm_const(data, offsetof(struct xdp_md, data)),
	  __imm_const(data_meta, offsetof(struct xdp_md, data_meta))
	: __clobber_all);
}

/* Two lookups in a 1-element array count as the same memory origin. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("header_count is 4 ")
__msg("widening r6 to 0..3 step 1")
__naked void ptr_map_value_two_lookups(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[small_map] ll;				\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r6 = r0;					\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[small_map] ll;				\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r7 = r0;					\
	r7 += 4;					\
1:	r6 += 1;					\
	if r6 < r7 goto 1b;				\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem),
	  __imm_addr(small_map)
	: __clobber_all);
}

/*
 * For inner array maps with BPF_F_INNER_MAP flag the actual array size
 * might differ from metadata in map declaration. Hence, r6 and r7 below
 * cannot be directly compared / iterations count can't be inferred.
 *
 *   r8 = bpf_map_lookup_elem(outer_map, ...); // inner map
 *   r6 = bpf_map_lookup_elem(r8, ...);
 *   r7 = bpf_map_lookup_elem(r8, ...);
 *   r7 += 4;
 *   do { r6++; ... } while (r6 < r7);
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("scev: incompatible latch operands r6 (map_value), r7 (map_value)")
__not_msg("widening r6")
__naked void ptr_map_value_two_lookups_inner_map(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[outer_map] ll;				\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r8 = r0;					\
	r2 = r10;					\
	r2 += -8;					\
	r1 = r8;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r6 = r0;					\
	r1 = r8;					\
	r2 = r10;					\
	r2 += -8;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r7 = r0;					\
	r7 += 4;					\
	r0 = 0;						\
1:	r6 += 1;					\
	r0 += 1;					\
	if r0 & 8 goto 2f;	/* main pass iteration guard */ \
	if r6 < r7 goto 1b;				\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem),
	  __imm_addr(outer_map)
	: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("header_count is 4 ")
__msg("widening r6 to 0..3 step 1")
__naked void ptr_map_value(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[map] ll;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r6 = r0;					\
	r7 = r6;					\
	r7 += 4;					\
1:	r6 += 1;					\
	if r6 < r7 goto 1b;				\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem), __imm_addr(map)
	: __clobber_all);
}

/* Equal offsets into different maps do not establish a common origin. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("scev: incompatible latch operands r6 (map_value), r7 (map_value)")
__not_msg("widening r6")
__naked void ptr_map_value_other_map(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[map] ll;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r6 = r0;					\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[other_map] ll;				\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto 2f;				\
	r7 = r0;					\
	r7 += 4;					\
	r0 = 0;						\
1:	r6 += 1;					\
	r0 += 1;					\
	if r0 & 8 goto 4f;				\
	if r6 < r7 goto 1b;				\
4:							\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem), __imm_addr(map), __imm_addr(other_map)
	: __clobber_all);
}

SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("header_count is 4 ")
__msg("widening r6 to 0..3 step 1")
__naked void ptr_mem(void)
{
	asm volatile ("					\
	r1 = %[ringbuf] ll;				\
	r2 = 8;						\
	r3 = 0;						\
	call %[bpf_ringbuf_reserve];			\
	if r0 == 0 goto 2f;				\
	r8 = r0;					\
	r6 = r0;					\
	r7 = r6;					\
	r7 += 4;					\
1:	r6 += 1;					\
	if r6 < r7 goto 1b;				\
	r1 = r8;					\
	r2 = 0;						\
	call %[bpf_ringbuf_discard];			\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_ringbuf_reserve), __imm(bpf_ringbuf_discard), __imm_addr(ringbuf)
	: __clobber_all);
}

/* Separate reservations have different pointer IDs. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("scev: incompatible latch operands r6 (ringbuf_mem), r7 (ringbuf_mem)")
__not_msg("widening r6")
__naked void ptr_mem_other_reservation(void)
{
	asm volatile ("					\
	r1 = %[ringbuf] ll;				\
	r2 = 8;						\
	r3 = 0;						\
	call %[bpf_ringbuf_reserve];			\
	if r0 == 0 goto 3f;				\
	r8 = r0;					\
	r6 = r0;					\
	r1 = %[ringbuf] ll;				\
	r2 = 8;						\
	r3 = 0;						\
	call %[bpf_ringbuf_reserve];			\
	if r0 == 0 goto 2f;				\
	r9 = r0;					\
	r7 = r0;					\
	r7 += 4;					\
	r0 = 0;						\
1:	r6 += 1;					\
	r0 += 1;					\
	if r0 & 8 goto 4f;				\
	if r6 < r7 goto 1b;				\
4:	r1 = r9;					\
	r2 = 0;						\
	call %[bpf_ringbuf_discard];			\
2:	r1 = r8;					\
	r2 = 0;						\
	call %[bpf_ringbuf_discard];			\
3:	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_ringbuf_reserve), __imm(bpf_ringbuf_discard), __imm_addr(ringbuf)
	: __clobber_all);
}

/* An access to a buffer at a variable offset is rejected: the pointer must not be widened. */
SEC("iter/bpf_map_elem")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("header_count is 4 ")
__msg("can't widen r6, expr is (+ r6 8)")
__naked void ptr_buf(void)
{
	asm volatile ("					\
	r6 = *(u64 *)(r1 + %[value]);			\
	if r6 == 0 goto 2f;				\
	r7 = 0;						\
1:	r0 = *(u32 *)(r6 + 0);				\
	r6 += 8;					\
	r7 += 1;					\
	if r7 < 4 goto 1b;				\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm_const(value, offsetof(struct bpf_iter__bpf_map_elem, value))
	: __clobber_all);
}

/* Separate context loads receive different pointer IDs. */
SEC("iter/bpf_map_elem")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("scev: incompatible latch operands r6 (buf), r7 (buf)")
__not_msg("widening r6")
__naked void ptr_buf_other_load(void)
{
	asm volatile ("					\
	r6 = *(u64 *)(r1 + %[value]);			\
	if r6 == 0 goto 2f;				\
	r7 = *(u64 *)(r1 + %[value]);			\
	if r7 == 0 goto 2f;				\
	r7 += 4;					\
	r0 = 0;						\
1:	r6 += 1;					\
	r0 += 1;					\
	if r0 & 8 goto 4f;				\
	if r6 < r7 goto 1b;				\
4:							\
2:	r0 = 0;						\
	exit;						\
"	:
	: __imm_const(value, offsetof(struct bpf_iter__bpf_map_elem, value))
	: __clobber_all);
}

/* A pointer-versus-scalar latch must not establish an iteration count. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("scev: incompatible latch operands r1 (map_value), scalar 4")
__not_msg("widening r1")
__naked void ptr_vs_scalar_no_widen(void)
{
	asm volatile ("					\
	*(u64 *)(r10 - 8) = 0;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[map] ll;					\
	call %[bpf_map_lookup_elem];			\
	if r0 == 0 goto out_%=;				\
	r1 = r0;					\
	r0 = 0;						\
loop_%=:						\
	r1 += 1;					\
	r0 += 1;					\
	if r0 & 8 goto out_%=;				\
	if r1 < 4 goto loop_%=;				\
out_%=:							\
	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem),
	  __imm_addr(map)
	: __clobber_all);
}

/* A nullable pointer must not be widened before its null check. */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop header at 9, can't widen r1, expr is (+ r1 8)")
__naked void no_widen_maybe_null(void)
{
	asm volatile ("					\
	r1 = 0;						\
	*(u64 *)(r10 - 8) = r1;				\
	r2 = r10;					\
	r2 += -8;					\
	r1 = %[map] ll;					\
	call %[bpf_map_lookup_elem];			\
	r1 = r0;					\
	r6 = 0;						\
loop_%=:						\
	if r1 == 0 goto exit_%=;			\
	r1 += 8;					\
	r6 += 1;					\
	if r6 < 3 goto loop_%=;				\
exit_%=:						\
	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem),
	  __imm_addr(map)
	: __clobber_all);
}

/*
 * A terminating inner loop does not prove termination of the outer loop.
 *
 *    u64 r7 = 0;
 *    while (bpf_get_prandom_u32() != 42) {
 *        r7 = (r7 + 1) & 0xf;
 *        u64 r8 = 0;
 *        do {
 *            r8++;
 *        } while (r8 < 3);
 *    }
 *    return 0;
 */
SEC("xdp")
__failure
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("The sequence of 8193 jumps is too complex.")
__naked void nested_terminating_prune(void)
{
	asm volatile ("					\
	r7 = 0;						\
outer_%=:						\
	r7 += 1;					\
	r7 &= 0xf;					\
	call %[bpf_get_prandom_u32];			\
	if r0 == 42 goto out_%=;			\
	r8 = 0;						\
inner_%=:						\
	r8 += 1;					\
	if r8 < 3 goto inner_%=;			\
	goto outer_%=;					\
out_%=:							\
	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * Returning directly from the inner loop to the outer header changes the
 * active stack from [1, 4] to [1].
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg("loop at 1{{$}}")
__msg("loop at 4, nested in 1")
__msg("entering loop 1")
__msg("entering loop 4")
__msg("exiting loop 4")
__not_msg("entering loop 1")
__msg("from 4 to 1:")
__msg("loop_stack=1{{$}}")
__naked void nested_loop_backedge_to_outer_header(void)
{
	asm volatile ("					\
	r6 = 0;						\
outer_%=:						\
	if r6 == 3 goto exit_%=;			\
	r6 += 1;					\
	r7 = 0;						\
inner_%=:						\
	if r7 == 2 goto outer_%=;			\
	r7 += 1;					\
	goto inner_%=;					\
exit_%=:						\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/* Induction variable as the src operand of the latch compare. */
SEC("socket")
__success
__log_level(2)
__msg("loop header at 2, header_count is 10")
__msg("loop header at 2, widening r1 to 0..9 step 1")
__flag(BPF_F_TEST_STATE_FREQ)
__naked void post_cond_ivar_src(void)
{
	asm volatile ("					\
	r1 = 0;						\
	r2 = 10;					\
1:	r1 += 1;					\
	if r2 != r1 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/* Early exit dominates the latch and gives a tighter bound. */
SEC("socket")
__success
__log_level(2)
__msg("  backedge from 4, latch at 4, dominating exits at 2")
__msg("loop header at 2, header_count is [0..15]")
__msg("loop header at 2, widening r1 to 0..14 step 1")
__flag(BPF_F_TEST_STATE_FREQ)
__naked void dominating_exit_bounds_count(void)
{
	asm volatile ("					\
	r1 = 0;						\
	r2 = 14;					\
1:	if r2 == r1 goto 2f;				\
	r1 += 1;					\
	if r1 != 63 goto 1b;				\
2:	r0 = 0;						\
	exit;						\
"	::: __clobber_all);
}

/*
 * The counter is copied to a callee-saved register for the call and the copy is compared.
 */
SEC("xdp")
__success
__log_level(2)
__flag(BPF_F_TEST_STATE_FREQ)
__msg(" scev at latch 5:")
__msg("  r7=(zext32 r1) / (zext32 (linear r1 2))")
__msg("loop header at 1, header_count is 100 ")
__msg("loop header at 1, widening r1 to 0..198 step 2")
__naked void post_cond_jlt32_copy(void)
{
	asm volatile ("					\
	w1 = 0;						\
1:	w7 = w1;					\
	call %[bpf_get_prandom_u32];			\
	w1 = w7;					\
	w1 += 2;					\
	if w7 < 198 goto 1b;				\
	r0 = 0;						\
	exit;						\
"	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

/*
 * r6 is a pointer to ringbuf memory with a step of 1. bpf_ringbuf_discard() in the first iteration
 * makes a number of it. The offsets 0..1 of the pointer are not the range of this number: it's an
 * address. The flag in the 32-bit spill is not widened, so the second iteration is verified
 * on its own.
 */
SEC("socket")
__failure __msg("math between map_value pointer and register with unbounded min value")
__naked void clamp_released_pointer(void)
{
	asm volatile (
	"r1 = 0;"
	"*(u32 *)(r10 - 12) = r1;"
	"r2 = r10;"
	"r2 += -12;"
	"r1 = %[small_map] ll;"
	"call %[bpf_map_lookup_elem];"
	"if r0 == 0 goto 9f;"
	"r8 = r0;"
	"r1 = %[ringbuf] ll;"
	"r2 = 16;"
	"r3 = 0;"
	"call %[bpf_ringbuf_reserve];"
	"if r0 == 0 goto 9f;"
	"r6 = r0;"
	"r7 = r0;"
	"r9 = 0;"
	"w1 = 0;"
	"*(u32 *)(r10 - 8) = r1;"
"1:"
	"w4 = *(u32 *)(r10 - 8);"
	"if w4 == 0 goto 2f;"
	"r1 = r8;"
	"r1 += r6;"
	"r0 = *(u8 *)(r1 + 0);"
	"goto 3f;"
"2:"
	"r1 = r7;"
	"r2 = 0;"
	"call %[bpf_ringbuf_discard];"
"3:"
	"w4 = 1;"
	"*(u32 *)(r10 - 8) = r4;"
	"r6 += 1;"
	"r9 += 1;"
	"if r9 < 2 goto 1b;"
"9:"
	"r0 = 0;"
	"exit;"
	:
	: __imm(bpf_map_lookup_elem), __imm(bpf_ringbuf_reserve), __imm(bpf_ringbuf_discard),
	  __imm_addr(small_map), __imm_addr(ringbuf)
	: __clobber_all);
}

/* The same with a packet pointer and bpf_skb_pull_data() */
SEC("tc")
__failure __msg("math between map_value pointer and register with unbounded min value")
__naked void clamp_invalidated_pkt_pointer(void)
{
	asm volatile (
	"r7 = r1;"
	"r1 = 0;"
	"*(u32 *)(r10 - 12) = r1;"
	"r2 = r10;"
	"r2 += -12;"
	"r1 = %[small_map] ll;"
	"call %[bpf_map_lookup_elem];"
	"if r0 == 0 goto 9f;"
	"r8 = r0;"
	"r6 = *(u32 *)(r7 + %[data]);"
	"r9 = 0;"
	"w1 = 0;"
	"*(u32 *)(r10 - 8) = r1;"
"1:"
	"w4 = *(u32 *)(r10 - 8);"
	"if w4 == 0 goto 2f;"
	"r1 = r8;"
	"r1 += r6;"
	"r0 = *(u8 *)(r1 + 0);"
	"goto 3f;"
"2:"
	"r1 = r7;"
	"r2 = 0;"
	"call %[bpf_skb_pull_data];"
"3:"
	"w4 = 1;"
	"*(u32 *)(r10 - 8) = r4;"
	"r6 += 1;"
	"r9 += 1;"
	"if r9 < 2 goto 1b;"
"9:"
	"r0 = 0;"
	"exit;"
	:
	: __imm(bpf_map_lookup_elem), __imm(bpf_skb_pull_data), __imm_addr(small_map),
	  __imm_const(data, offsetof(struct __sk_buff, data))
	: __clobber_all);
}

/*
 * The compare with data_end is for r6 of this iteration: 100 bytes from r6 are in the packet. Then
 * r6 moves by 100. The range that the compare found is not for the r6 that returns to the head.
 */
SEC("tc")
__failure __msg("invalid access to packet")
__naked void clamp_pkt_pointer_keeps_no_range(void)
{
	asm volatile (
	"r7 = *(u32 *)(r1 + %[data_end]);"
	"r6 = *(u32 *)(r1 + %[data]);"
	"r9 = 0;"
	"w1 = 0;"
	"*(u32 *)(r10 - 8) = r1;"
"1:"
	"w4 = *(u32 *)(r10 - 8);"
	"if w4 == 0 goto 2f;"
	/* second iteration: nothing compared this r6 with data_end */
	"r0 = *(u64 *)(r6 + 56);"
"2:"
	"r5 = r6;"
	"r5 += 100;"
	"if r5 > r7 goto 9f;"
	"w4 = 1;"
	"*(u32 *)(r10 - 8) = r4;"
	"r6 += 100;"
	"r9 += 1;"
	"if r9 < 2 goto 1b;"
"9:"
	"r0 = 0;"
	"exit;"
	:
	: __imm_const(data, offsetof(struct __sk_buff, data)),
	  __imm_const(data_end, offsetof(struct __sk_buff, data_end))
	: __clobber_all);
}

/* A compare in front of the loop is for all iterations: the range at the entry stays */
SEC("tc")
__success __retval(0)
__naked void clamp_pkt_pointer_keeps_range_of_entry(void)
{
	asm volatile (
	"r7 = *(u32 *)(r1 + %[data_end]);"
	"r6 = *(u32 *)(r1 + %[data]);"
	"r5 = r6;"
	"r5 += 40;"
	"if r5 > r7 goto 9f;"
	"r9 = 0;"
"1:"
	"r0 = *(u64 *)(r6 + 0);"
	"r6 += 8;"
	"r9 += 1;"
	"if r9 < 4 goto 1b;"
"9:"
	"r0 = 0;"
	"exit;"
	:
	: __imm_const(data, offsetof(struct __sk_buff, data)),
	  __imm_const(data_end, offsetof(struct __sk_buff, data_end))
	: __clobber_all);
}

/*
 * r4 is 0, 8 .. 48, but its umax is 50. @bytes from r6 are in the packet: the range of r6 is
 * @start + 50 + @bytes.
 */
#define PKT_PLUS_R4(start, bytes)					\
	"r7 = *(u32 *)(r1 + %[data_end]);"				\
	"r6 = *(u32 *)(r1 + %[data]);"					\
	"r4 = *(u32 *)(r1 + %[mark]);"					\
	"r4 &= 0x38;"							\
	"if r4 > 50 goto 9f;"						\
	"r6 += " #start ";"						\
	"r6 += r4;"							\
	"r5 = r6;"							\
	"r5 += " #bytes ";"						\
	"if r5 > r7 goto 9f;"

#define PKT_IMMS							\
	__imm_const(data, offsetof(struct __sk_buff, data)),		\
	__imm_const(data_end, offsetof(struct __sk_buff, data_end)),	\
	__imm_const(mark, offsetof(struct __sk_buff, mark))

/*
 * r6 is 0..58 at the head, and 0..56 with the step of 8. The range must go from 58 to 56 too:
 * in the second iteration no byte from r6 is in the packet.
 */
SEC("tc")
__failure __msg("invalid access to packet, off=56 size=2, R6(id=2,off=56,r=56)")
__naked void widen_pkt_pointer_step_lowers_umax(void)
{
	asm volatile (
	PKT_PLUS_R4(0, 8)
	"r9 = 0;"
"1:"
	"r0 = *(u16 *)(r6 + 0);"
	"r6 += 8;"
	"r9 += 1;"
	"if r9 < 2 goto 1b;"
"9:"
	"r0 = 0;"
	"exit;"
	:: PKT_IMMS : __clobber_all);
}

/* The pointer goes down. 8 bytes from the first r6 are in the packet, not 10. */
SEC("tc")
__failure __msg("invalid access to packet, off=120 size=2, R6(id=2,off=120,r=120)")
__naked void widen_pkt_pointer_step_lowers_umax_down(void)
{
	asm volatile (
	PKT_PLUS_R4(64, 8)
	"r9 = 0;"
"1:"
	"r0 = *(u16 *)(r6 + 8);"
	"r6 += -8;"
	"r9 += 1;"
	"if r9 < 2 goto 1b;"
"9:"
	"r0 = 0;"
	"exit;"
	:: PKT_IMMS : __clobber_all);
}

/*
 * r6 is -8..50 at the head, and -8..48 with the step of 8. Its umax is U64_MAX in the two cases.
 * r5 is 0..56 and has the range of r6. In the first iteration no byte from r5 is in the packet.
 */
SEC("tc")
__failure __msg("invalid access to packet, off=56 size=2, R5(id=2,off=56,r=56)")
__naked void widen_pkt_pointer_negative_offset(void)
{
	asm volatile (
	PKT_PLUS_R4(0, 8)
	"r9 = 0;"
"1:"
	"r5 = r6;"
	"r5 += 8;"
	"r0 = *(u16 *)(r5 + 0);"
	"r6 += -8;"
	"r9 += 1;"
	"if r9 < 2 goto 1b;"
"9:"
	"r0 = 0;"
	"exit;"
	:: PKT_IMMS : __clobber_all);
}

/* The access is in the second iteration only: the verifier gets to it after the clamp */
SEC("tc")
__failure __msg("invalid access to packet, off=56 size=2, R6(id=3,off=56,r=56)")
__naked void clamp_pkt_pointer_step_lowers_umax(void)
{
	asm volatile (
	PKT_PLUS_R4(0, 8)
	"r9 = 0;"
	"w1 = 0;"
	"*(u32 *)(r10 - 8) = r1;"
"1:"
	"w1 = *(u32 *)(r10 - 8);"
	"if w1 == 0 goto 2f;"
	"r0 = *(u16 *)(r6 + 0);"
"2:"
	"w1 = 1;"
	"*(u32 *)(r10 - 8) = r1;"
	"r6 += 8;"
	"r9 += 1;"
	"if r9 < 2 goto 1b;"
"9:"
	"r0 = 0;"
	"exit;"
	:: PKT_IMMS : __clobber_all);
}

/* r5 is r5 = r6 + 8 or r6 at the head. Here var_off lowers umax. No byte from r6 + 8 is valid. */
SEC("tc")
__failure __msg("invalid access to packet, off=56 size=2, R5(id=2,off=56,r=56)")
__naked void union_pkt_pointer_var_off_lowers_umax(void)
{
	asm volatile (
	PKT_PLUS_R4(0, 8)
	"r9 = 0;"
"1:"
	"r0 = *(u16 *)(r5 + 0);"
	"r5 = r6;"
	"r9 += 1;"
	"if r9 < 2 goto 1b;"
"9:"
	"r0 = 0;"
	"exit;"
	:: PKT_IMMS : __clobber_all);
}

/* 16 bytes from r6 are in the packet: two iterations read 8 bytes each */
SEC("tc")
__success __retval(0)
__naked void widen_pkt_pointer_keeps_valid_bytes(void)
{
	asm volatile (
	PKT_PLUS_R4(0, 16)
	"r9 = 0;"
"1:"
	"r0 = *(u64 *)(r6 + 0);"
	"r6 += 8;"
	"r9 += 1;"
	"if r9 < 2 goto 1b;"
"9:"
	"r0 = 0;"
	"exit;"
	:: PKT_IMMS : __clobber_all);
}

/*
 * r6 is beyond pkt_end in front of the loop and comes back into the packet. The mark is not for
 * all iterations: the verifier must look at the two branches of the compare in the first pass.
 */
SEC("tc")
__success
__log_level(2)
__msg("widening r6 to 32..96 step 32")
__msg("6: R6=pkt(id=1,r=0,smin=umin=smin32=umin32=32,smax=umax=smax32=umax32=96")
__naked void widen_pkt_pointer_beyond_pkt_end(void)
{
	asm volatile (
	"r7 = *(u32 *)(r1 + %[data_end]);"
	"r6 = *(u32 *)(r1 + %[data]);"
	"r6 += 96;"
	"if r6 > r7 goto 1f;"
	"goto 9f;"
"1:"
	"r9 = 0;"
"2:"
	"if r6 > r7 goto 3f;"
	"r0 = *(u8 *)(r6 - 1);"
"3:"
	"r6 += -32;"
	"r9 += 1;"
	"if r9 < 3 goto 2b;"
"9:"
	"r0 = 0;"
	"exit;"
	:: PKT_IMMS : __clobber_all);
}

char _license[] SEC("license") = "GPL";