Merge branch 'bpf-support-32-bit-linear-scalar-evolution'

Eduard Zingerman says:

====================
bpf: support 32-bit linear scalar evolution

Support scalar evolution widening for loops like:

     w0 = 0;
  l: w0 += 1;
     if w0 != 3 goto l;
     exit;

Implementation details are covered in the first patch.
Veristat results follow. Program sets: cilium, meta, scx, selftests.
Tables: success in both runs; baseline Insns >= 5,000.
Ranked by percentage change, then instruction-count change, file,
program. Meta names are anonymized.
Top 50 wins are shown, there are no loses.

Histogram
---------

Total progs: 7994
Old success: 5665
New success: 5665
-100 .. -95  %: 21
 -95 .. -85  %: 1
 -85 .. -75  %: 4
 -75 .. -70  %: 17
 -70 .. -65  %: 10
 -65 .. -55  %: 3
 -50 .. -40  %: 2
 -40 .. -30  %: 2
 -25 .. -15  %: 2
 -15 .. -10  %: 7
 -10 .. -5   %: 32
  -5 .. 0    %: 6
   0 .. 5    %: 7887

Top wins (50)
-------------

File                           Program                            Insns (A)  Insns (B)       Insns (DIFF)
-----------------------------  ---------------------------------  ---------  ---------  -----------------
timer_start_delete_race.bpf.o  start_timer                            40007         28   -39979 (-99.93%)
timer_start_delete_race.bpf.o  delete_elem                            14003         11   -13992 (-99.92%)
verifier_bounds.bpf.o          crossing_32_bit_signed_boundary_2      12330         20   -12310 (-99.84%)
access_map_in_map.bpf.o        access_map_in_array                    18457         35   -18422 (-99.81%)
access_map_in_map.bpf.o        access_map_in_htab                     18457         35   -18422 (-99.81%)
access_map_in_map.bpf.o        sleepable_access_map_in_array          18457         35   -18422 (-99.81%)
access_map_in_map.bpf.o        sleepable_access_map_in_htab           18457         35   -18422 (-99.81%)
firewall-09.bpf.o              twfw_connect6                         153638        320  -153318 (-99.79%)
firewall-09.bpf.o              twfw_sendmsg6                         153638        320  -153318 (-99.79%)
firewall-10.bpf.o              twfw_connect4                         102193        241  -101952 (-99.76%)
firewall-10.bpf.o              twfw_sendmsg4                         102193        241  -101952 (-99.76%)
firewall-10.bpf.o              twfw_connect6                         166183        397  -165786 (-99.76%)
firewall-10.bpf.o              twfw_sendmsg6                         166183        397  -165786 (-99.76%)
firewall-09.bpf.o              twfw_connect4                          76030        197   -75833 (-99.74%)
firewall-09.bpf.o              twfw_sendmsg4                          76030        197   -75833 (-99.74%)
linked_list.bpf.o              clear_global_array_list                13071         57   -13014 (-99.56%)
rhash.bpf.o                    test_rhash_update_elements              7584         91    -7493 (-98.80%)
profiler-06.bpf.o              on_perf_event                         425953      94751  -331202 (-77.76%)
profiler-26.bpf.o              handle_cu_mem_address_reserve          45724      12702   -33022 (-72.22%)
profiler-26.bpf.o              handle_cu_mem_create                   45724      12702   -33022 (-72.22%)
profiler-26.bpf.o              handle_malloc                          45724      12702   -33022 (-72.22%)
profiler-19.bpf.o              sched_switch_offcpu                    78210      21906   -56304 (-71.99%)
profiler-26.bpf.o              handle_cu_mem_map                      45922      12900   -33022 (-71.91%)
profiler-09.bpf.o              on_custom_event_start                  45973      12951   -33022 (-71.83%)
profiler-09.bpf.o              trace_func_entry                       45973      12951   -33022 (-71.83%)
profiler-19.bpf.o              sched_waking                           23153       6642   -16511 (-71.31%)
profiler-27.bpf.o              handle_cuda_launch_exc                 23176       6665   -16511 (-71.24%)
profiler-27.bpf.o              handle_cuda_launch                     23189       6678   -16511 (-71.20%)
profiler-12.bpf.o              on_custom_event_begin                  23396       6885   -16511 (-70.57%)
profiler-12.bpf.o              on_custom_event_end                    23400       6889   -16511 (-70.56%)
profiler-26.bpf.o              handle_mtia_cached_alloc               46892      13870   -33022 (-70.42%)
profiler-26.bpf.o              handle_mtia_allocate_enter             46953      13931   -33022 (-70.33%)
profiler-12.bpf.o              sched_switch                           40257      12105   -28152 (-69.93%)
profiler-26.bpf.o              handle_pytorch_malloc                  47245      14223   -33022 (-69.90%)
profiler-19.bpf.o              oncpu                                  23689       7178   -16511 (-69.70%)
profiler-12.bpf.o              on_task_enqueued                       23734       7223   -16511 (-69.57%)
profiler-12.bpf.o              sched_waking                           23769       7258   -16511 (-69.46%)
profiler-12.bpf.o              on_task_dequeued                       23909       7398   -16511 (-69.06%)
profiler-12.bpf.o              on_request_context_event               24000       7489   -16511 (-68.80%)
profiler-12.bpf.o              on_pytorch_event                       24001       7490   -16511 (-68.79%)
profiler-12.bpf.o              on_task_stats                          24083       7572   -16511 (-68.56%)
profiler-12.bpf.o              oncpu                                  24187       7676   -16511 (-68.26%)
scx_rusty.bpf.o                rusty_init                              8784       3171    -5613 (-63.90%)
profiler-12.bpf.o              get_crochet_walltime_stacks            50215      22063   -28152 (-56.06%)
security-sandbox-13.bpf.o      kvm_die                                 5807       2967    -2840 (-48.91%)
profiler-24.bpf.o              get_task_stacks                       103742      64928   -38814 (-37.41%)
scheduler-01.bpf.o             arena_alloc_mask                       29208      25497    -3711 (-12.71%)
scheduler-03.bpf.o             arena_alloc_mask                       29208      25497    -3711 (-12.71%)
file-system-monitor-01.bpf.o   file_lineage_lsm_file_free             20986      18354    -2632 (-12.54%)
file-system-monitor-01.bpf.o   file_lineage_security_file_free        20986      18354    -2632 (-12.54%)
---
====================

Link: https://patch.msgid.link/20261020-scev-32bit-v1-0-838f34f9f0cd@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

2 files changed, 262 insertions, 108 deletions

diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
index 48500d73105a..fea77772ca96 100644
--- a/kernel/bpf/scev.c
+++ b/kernel/bpf/scev.c
@@ -249,6 +249,14 @@ static bool is_linear(struct scev *scev, int id, u32 *base, u32 *slope)
 	return is_binop(scev, LINEAR_SCEV, id, base, slope);
 }
 
+static bool is_linear_or_linear32(struct scev *scev, int id, u32 *base, u32 *slope, bool *zext32)
+{
+	u32 t;
+
+	*zext32 = is_zext32(scev, id, &t);
+	return is_linear(scev, *zext32 ? t : id, base, slope);
+}
+
 static bool is_opaque(struct scev *scev, int id)
 {
 	return is_op(scev, id, OPAQUE);
@@ -1464,7 +1472,7 @@ static int transform_expr(struct scev *scev, u32 root, void *priv,
 
 static int simplify(struct scev *scev, u32 id, void *priv)
 {
-	u32 l, r, base, slope;
+	int a, b, l, r, t, base, slope;
 	s64 imm1, imm2;
 
 	/* (+ (linear base slope) imm) -> (linear (+ base imm) slope) */
@@ -1483,13 +1491,24 @@ static int simplify(struct scev *scev, u32 id, void *priv)
 	if (is_zext32(scev, id, &l) && is_imm(scev, l, &imm1))
 		return imm_expr(scev, (u64)(u32)imm1);
 
+	/*
+	 * (zext32 (+ (zext32 $a) $b)) -> (zext32 (+ $a $b))
+	 * (zext32 (+ $a (zext32 $b))) -> (zext32 (+ $a $b))
+	 */
+	if ((is_zext32(scev, id, &t) && is_add(scev, t, &l, &b) && is_zext32(scev, l, &a)) ||
+	    (is_zext32(scev, id, &t) && is_add(scev, t, &a, &r) && is_zext32(scev, r, &b))) {
+		t = expr2(scev, BPF_ADD, a, b);
+		t = expr1(scev, ZEXT32, t);
+		return t;
+	}
+
 	return id;
 }
 
 static int compute_header_scevs(struct bpf_verifier_env *env, struct env *header_env)
 {
 	struct scev *scev = env->scev;
-	int l, r, id, ra, rb, ra_expr;
+	int l, r, t, id, ra, rb, ra_expr;
 	s64 imm;
 
 	/*
@@ -1522,6 +1541,19 @@ static int compute_header_scevs(struct bpf_verifier_env *env, struct env *header
 			header_env->reg2scev[ra] = id;
 			continue;
 		}
+		/* rA = (is_zext32 (+ rA IMM)) -> (is_zext32 (linear rA IMM)) */
+		if (is_zext32(scev, ra_expr, &t) &&
+		    is_add(scev, t, &l, &r) &&
+		    is_reg(scev, l, &rb) &&
+		    is_imm(scev, r, &imm) &&
+		    ra == rb) {
+			id = expr2(scev, LINEAR_SCEV, l, r);
+			id = expr1(scev, ZEXT32, id);
+			if (id < 0)
+				return id;
+			header_env->reg2scev[ra] = id;
+			continue;
+		}
 		/* rA = rA -> rA*/
 		if (is_reg(scev, ra_expr, &rb) && ra == rb) {
 			header_env->reg2scev[ra] = ra_expr;
@@ -1846,13 +1878,17 @@ static bool scev_reg_alive(struct bpf_verifier_env *env, struct bpf_verifier_sta
  * Linear latch represents a condition 'if <reg> <op> <loop invariant> goto <loop-header>',
  * where equation '<base> + i * <step> <op> <bound>' describes values taken by register <reg>,
  * 'i' is the loop iteration number, starting from 0.
+ * 'zext32' indicates the latch is for (zext32 (linear ...)) SCEV.
+ * 'jmp32' indicates that the latch is a JMP32 instruction.
  */
 struct linear_latch {
 	u32 insn_idx;
 	u32 base_expr;
 	u32 step_expr;
 	u32 bound_expr;
-	u32 op;
+	u8 op;
+	bool zext32;
+	bool jmp32;
 };
 
 static bool loop_invariant(struct scev *scev, u32 id)
@@ -1878,10 +1914,8 @@ static int match_linear_latch(struct bpf_verifier_env *env,
 	u32 t, l, r, op;
 	int id;
 
-	/* 32-bit arithmetic is not handled yet */
-	if (BPF_CLASS(insn->code) != BPF_JMP)
-		return false;
 	op = BPF_OP(insn->code);
+	latch->jmp32 = BPF_CLASS(insn->code) == BPF_JMP32;
 	/* Flip the condition if true branch jumps out of the loop. */
 	true_branch_tgt = latch_idx + bpf_jmp_offset(insn) + 1;
 	true_branch_loop = bpf_loop_at_index(env, true_branch_tgt);
@@ -1915,7 +1949,8 @@ static int match_linear_latch(struct bpf_verifier_env *env,
 	 *   'if <invariant> <op> <linear>' ⇔
 	 * 'if <linear> <flip(op)> <invariant>'.
 	 */
-	if (BPF_SRC(insn->code) == BPF_X && is_linear(scev, src_reg_scev, &l, &r)) {
+	if (BPF_SRC(insn->code) == BPF_X &&
+	    is_linear_or_linear32(scev, src_reg_scev, &l, &r, &latch->zext32)) {
 		swap(dst_reg_scev, src_reg_scev);
 		op = bpf_flip_opcode(op);
 	}
@@ -1928,7 +1963,8 @@ static int match_linear_latch(struct bpf_verifier_env *env,
 	 * - (linear (+ register imm) step)       |
 	 *           ^----------------------------'
 	 */
-	if (!is_linear(scev, dst_reg_scev, &latch->base_expr, &latch->step_expr))
+	if (!is_linear_or_linear32(scev, dst_reg_scev,
+				   &latch->base_expr, &latch->step_expr, &latch->zext32))
 		return false;
 
 	if (BPF_SRC(insn->code) == BPF_K) {
@@ -2049,64 +2085,23 @@ static bool eval_expr(struct bpf_verifier_env *env, struct scev *scev,
 	return false;
 }
 
-/*
- * Loop with post-condition:
- *
- *    r0 = 0
- * l: ...                r0 ∈ [0,1,2] header executed 3 times
- *    r0 += 1            r0 ∈ [0,1,2]
- *    ...                r0 ∈ [1,2,3]
- *    if r0 != 3 goto l  r0 ∈ [1,2,3] backedge taken 2 times
- *    ...                r0 ∈ [3]
- *
- * SCEV at header: r0 = k
- * SCEV at latch:  r0 = 1 + k
- *
- * Loop with pre-condition:
- *
- *    r0 = 0
- * l: ...                r0 ∈ [0,1,2,3] header executed 4 times
- *    if r0 == 3 goto e  r0 ∈ [0,1,2,3] backedge taken 3 times
- *    r0 += 1            r0 ∈ [0,1,2]
- *    ...                r0 ∈ [1,2,3]
- *    goto l             r0 ∈ [1,2,3]
- * e: ...                r0 ∈ [3]
- *
- * SCEV at header: r0 = k
- * SCEV at latch:  r0 = k
- */
-static bool compute_max_iters(struct bpf_verifier_env *env,
-			      struct bpf_func_state *st,
-			      struct linear_latch *latch,
-			      struct bpf_loop_iters *iters)
+static bool is_signed_op(u8 op)
 {
-	struct bpf_insn_aux_data *aux = env->insn_aux_data;
-	struct bpf_loop *loop = aux[bpf_loop_at_index(env, latch->insn_idx)].loop;
-	struct scev *scev = env->scev;
-	struct scev_value initial_val, step_val, bound_val;
-	u64 rem, step, diff, bound, initial, backedge_taken_count;
-	u8 op = latch->op;
-	bool up, down;
-
-	if (!eval_expr(env, scev, st, latch->base_expr, &initial_val) ||
-	    !eval_expr(env, scev, st, latch->step_expr, &step_val) ||
-	    !eval_expr(env, scev, st, latch->bound_expr, &bound_val))
-		return false;
-
-	if (step_val.ptr_reg >= 0) {
-		if (env->log.level & BPF_LOG_LEVEL2) {
-			bpf_log(&env->log, "scev: latch step is a pointer ");
-			log_scev_value(env, st, &step_val);
-			bpf_log(&env->log, "\n");
-		}
+	switch (op) {
+	case BPF_JSLT:
+	case BPF_JSLE:
+	case BPF_JSGT:
+	case BPF_JSGE:
+		return true;
+	default:
 		return false;
 	}
-	if (!scev_value_compatible(env, st, &initial_val, &bound_val))
-		return false;
+}
 
-	initial = initial_val.value;
-	step = step_val.value;
-	bound = bound_val.value;
+static bool compute_backedge_taken_count(u8 op, u64 initial, u64 step, u64 bound, u64 *result)
+{
+	u64 rem, diff, backedge_taken_count;
+	bool up, down;
 
 	if (step == 0)
 		return false;
@@ -2217,6 +2212,115 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
 		return false;
 	}
 
+	*result = backedge_taken_count;
+	return true;
+}
+
+/*
+ * Loop with post-condition:
+ *
+ *    r0 = 0
+ * l: ...                r0 ∈ [0,1,2] header executed 3 times
+ *    r0 += 1            r0 ∈ [0,1,2]
+ *    ...                r0 ∈ [1,2,3]
+ *    if r0 != 3 goto l  r0 ∈ [1,2,3] backedge taken 2 times
+ *    ...                r0 ∈ [3]
+ *
+ * SCEV at header: r0 = k
+ * SCEV at latch:  r0 = 1 + k
+ *
+ * Loop with pre-condition:
+ *
+ *    r0 = 0
+ * l: ...                r0 ∈ [0,1,2,3] header executed 4 times
+ *    if r0 == 3 goto e  r0 ∈ [0,1,2,3] backedge taken 3 times
+ *    r0 += 1            r0 ∈ [0,1,2]
+ *    ...                r0 ∈ [1,2,3]
+ *    goto l             r0 ∈ [1,2,3]
+ * e: ...                r0 ∈ [3]
+ *
+ * SCEV at header: r0 = k
+ * SCEV at latch:  r0 = k
+ */
+static bool compute_max_iters(struct bpf_verifier_env *env,
+			      struct bpf_func_state *st,
+			      struct linear_latch *latch,
+			      struct bpf_loop_iters *iters)
+{
+	struct bpf_insn_aux_data *aux = env->insn_aux_data;
+	struct bpf_loop *loop = aux[bpf_loop_at_index(env, latch->insn_idx)].loop;
+	struct scev *scev = env->scev;
+	struct scev_value initial_val, step_val, bound_val;
+	u64 step, bound, initial, total_change, backedge_taken_count;
+	u8 op = latch->op;
+
+	if (!eval_expr(env, scev, st, latch->base_expr, &initial_val) ||
+	    !eval_expr(env, scev, st, latch->step_expr, &step_val) ||
+	    !eval_expr(env, scev, st, latch->bound_expr, &bound_val))
+		return false;
+
+	if (step_val.ptr_reg >= 0) {
+		if (env->log.level & BPF_LOG_LEVEL2) {
+			bpf_log(&env->log, "scev: latch step is a pointer ");
+			log_scev_value(env, st, &step_val);
+			bpf_log(&env->log, "\n");
+		}
+		return false;
+	}
+	if (!scev_value_compatible(env, st, &initial_val, &bound_val))
+		return false;
+
+	initial = initial_val.value;
+	step = step_val.value;
+	bound = bound_val.value;
+
+	/*
+	 * The code below only handles mixed 64-bit/32-bit comparisons/recurrences
+	 * when initial bounds and step fit in 32-bit domain.
+	 */
+	if (latch->zext32 || latch->jmp32) {
+		/*
+		 * With the above constraint doing `l: w0 += 1; if r0 s< 256 goto l;`
+		 *                is equivalent to `l: w0 += 1; if r0 < 256 goto l;`
+		 */
+		if (latch->jmp32 && is_signed_op(op)) {
+			initial = (s64)(s32)(u32)initial;
+			bound   = (s64)(s32)(u32)bound;
+			step    = (s64)(s32)(u32)step;
+		} else {
+			initial = (u32)initial;
+			bound   = (u32)bound;
+			step    = (s64)(s32)(u32)step;
+		}
+	}
+	if (latch->zext32 ^ latch->jmp32 && (initial != initial_val.value ||
+					     bound != bound_val.value ||
+					     step != step_val.value)) {
+		if (env->log.level & BPF_LOG_LEVEL2)
+			bpf_log(&env->log,
+				"scev: mixed-width latch has operands outside 32-bit ranges\n");
+		return false;
+	}
+
+
+	if (!compute_backedge_taken_count(op, initial, step, bound, &backedge_taken_count))
+		return false;
+
+	if (latch->zext32 || latch->jmp32) {
+		/*
+		 * compute_backedge_taken_count() guarantees that 'total_change'
+		 * does not overflow in 64-bit domain.
+		 */
+		total_change = initial + step * backedge_taken_count;
+		if (latch->jmp32 && is_signed_op(op)) {
+			if ((s64)total_change < S32_MIN || (s64)total_change > S32_MAX)
+				return false;
+		} else {
+			if (total_change > U32_MAX)
+				return false;
+		}
+	}
+
 	/*
 	 * max_header_count is u32 and U32_MAX means "infinite",
 	 * check to avoid overflow below.
@@ -2337,40 +2441,92 @@ static bool is_widenable_any(struct bpf_verifier_env *env, struct bpf_func_state
 }
 
 struct bounds {
-	struct cnum64 range;
+	struct cnum64 r64;
+	struct cnum32 r32;
 	u16 base;
 	u16 step;
 };
 
-static bool is_simple_linear(struct scev *scev, u32 id, u32 *base_reg, s64 *slope_imm)
+static void log_bounds(struct bpf_verifier_env *env, const struct bounds *bounds)
+{
+	struct bpf_verifier_log *log = &env->log;
+
+	bpf_verbose_snum(env, cnum64_smin(bounds->r64));
+	bpf_log(log, "..");
+	bpf_verbose_snum(env, cnum64_smax(bounds->r64));
+	if (bounds->r32.size < U32_MAX) {
+		bpf_log(log, " (s32 ");
+		bpf_verbose_snum(env, cnum32_smin(bounds->r32));
+		bpf_log(log, "..");
+		bpf_verbose_snum(env, cnum32_smax(bounds->r32));
+		bpf_log(log, ")");
+	}
+	bpf_log(log, " step %u", bounds->step);
+}
+
+struct linear_coefs {
+	u32 base_reg;
+	s64 slope;
+	bool zext32;
+};
+
+static bool is_simple_linear(struct scev *scev, u32 id, struct linear_coefs *out)
 {
 	u32 base, slope;
 
-	return is_linear(scev, id, &base, &slope) &&
-	       is_reg(scev, base, base_reg) &&
-	       is_imm(scev, slope, slope_imm) &&
-	       *slope_imm <= S16_MAX &&
-	       *slope_imm >= S16_MIN &&
-	       *slope_imm != 0;
+	return is_linear_or_linear32(scev, id, &base, &slope, &out->zext32) &&
+	       is_reg(scev, base, &out->base_reg) &&
+	       is_imm(scev, slope, &out->slope) &&
+	       out->slope <= S16_MAX &&
+	       out->slope >= S16_MIN &&
+	       out->slope != 0;
 }
 
-/*
- * Compute the range an induction variable in `reg` spans over the loop.
- * If the computation overflows s64 the range is unbounded, only the
- * power-of-two alignment survives the wraparound.
- */
-static void linear_bounds(struct bpf_reg_state *reg, u32 max_header_count, s64 slope,
-			  struct bounds *out)
+static struct cnum64 cnum64_zext32(struct cnum32 r32)
+{
+	return cnum64_from_urange(cnum32_umin(r32), cnum32_umax(r32));
+}
+
+/* Compute the range an induction variable in `reg` spans over the loop. */
+static void linear_bounds(struct bpf_reg_state *reg, u32 max_header_count,
+			  struct linear_coefs *coefs, struct bounds *out)
 {
+	s64 slope = coefs->slope;
 	s64 slope_abs = slope < 0 ? -slope : slope;
 	s64 min_val = reg_smin(reg);
 	s64 max_val = reg_smax(reg);
+	struct cnum64 r64;
+	struct cnum32 r32;
 	s64 total_change;
 	bool overflow;
 
 	overflow = check_mul_overflow(slope, (s64)max_header_count - 1, &total_change) ||
 		   (slope > 0 && check_add_overflow(max_val, total_change, &max_val)) ||
 		   (slope < 0 && check_add_overflow(min_val, total_change, &min_val));
+	r64 = overflow ? CNUM64_UNBOUNDED : cnum64_from_srange(min_val, max_val);
+	r32 = CNUM32_UNBOUNDED;
+	if (coefs->zext32) {
+		r32 = cnum32_from_cnum64(r64);
+		r64 = cnum64_zext32(r32);
+		/*
+		 * 32-bit iteration overflow is equivalent to subtracting N * 2**32:
+		 * (base + slope * k) % slope ≠ (base + slope * k - N * 2**32) % slope.
+		 */
+		overflow |= cnum32_contains(r32, 0) && cnum32_contains(r32, U32_MAX);
+		/*
+		 * The entry and zero-extended values must agree on how they define `base`,
+		 * otherwise `base + slope * k` would define different sets of points between
+		 * the two.
+		 */
+		overflow |= imod(reg_smin(reg), slope_abs) !=
+			    imod(cnum64_smin(r64), slope_abs);
+		/*
+		 * Full range is a union of a reg's value at loop entry,
+		 * plus a range produced by 32-bit iteration.
+		 */
+		r64 = cnum64_union(reg->r64, r64);
+		r32 = cnum32_union(reg->r32, r32);
+	}
 	/*
 	 * If the entry value is a single point the value set is 'v + slope * k',
 	 * so the step is |slope|. Otherwise, only the power-of-two alignment
@@ -2378,12 +2534,13 @@ static void linear_bounds(struct bpf_reg_state *reg, u32 max_header_count, s64 s
 	 */
 	if (cnum64_is_const(reg->r64) && !overflow) {
 		out->step = slope_abs;
-		out->base = imod(min_val, out->step);
+		out->base = imod(reg_smin(reg), out->step);
 	} else {
 		out->step = 1u << min_t(u32, tnum_alignment(reg->var_off), __ffs(slope_abs));
 		out->base = 0;
 	}
-	out->range = overflow ? CNUM64_UNBOUNDED : cnum64_from_srange(min_val, max_val);
+	out->r64 = r64;
+	out->r32 = r32;
 }
 
 static int mark_expr_precise(struct bpf_verifier_env *env, struct bpf_func_state *st, u32 id,
@@ -2419,16 +2576,16 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta
 	struct scev *scev = env->scev;
 	struct env *header_env;
 	struct linear_latch latch, best;
+	struct linear_coefs coefs;
 	struct bpf_backedge *backedge;
 	struct bpf_loop_iters tmp;
 	struct bpf_loop *loop;
 	int insn_idx = st->insn_idx;
 	bool found = false;
 	int linear_latch;
-	u32 r, base_reg;
 	int latch_idx;
-	s64 slope_imm;
 	int err, j;
+	u32 r;
 
 	if (!env->allow_uninit_stack)
 		return 0;
@@ -2542,8 +2699,7 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta
 		r_scev = header_env->reg2scev[r];
 		reg = scev_reg_for_linear(cur_func, r);
 		/* If SCEV for r is (linear <reg> <slope>) */
-		if (is_simple_linear(scev, r_scev, &base_reg, &slope_imm) &&
-		    reg && is_widenable_reg_type(reg)) {
+		if (reg && is_simple_linear(scev, r_scev, &coefs) && is_widenable_reg_type(reg)) {
 			/* Spills at varying offsets lose precision */
 			if (test_bit(r, loop->store_base_regs)) {
 				spill_base = true;
@@ -2639,10 +2795,10 @@ int bpf_widen_scev_regs(struct bpf_verifier_env *env, struct bpf_verifier_state
 	struct scev *scev = env->scev;
 	struct bpf_reg_state *reg;
 	struct env *header_env;
+	struct linear_coefs coefs;
 	struct bounds bounds;
-	u32 r, base_reg, r_expr, a, b;
+	u32 r, r_expr, a, b;
 	int insn_idx = st->insn_idx;
-	s64 slope_imm;
 	int err;
 
 	for_each_set_bit(r, iters->precise_regs, REGS_NUM) {
@@ -2662,23 +2818,21 @@ int bpf_widen_scev_regs(struct bpf_verifier_env *env, struct bpf_verifier_state
 
 		r_expr = header_env->reg2scev[r];
 		/* If SCEV for r is (linear <reg> <slope>)*/
-		if (is_simple_linear(scev, r_expr, &base_reg, &slope_imm) &&
-		    base_reg == r) {
+		if (is_simple_linear(scev, r_expr, &coefs) && coefs.base_reg == r) {
 			err = scev_reg_for_write(env, cur_func, r, &reg);
 			if (err)
 				return err;
-			linear_bounds(reg, iters->max_header_count, slope_imm, &bounds);
+			linear_bounds(reg, iters->max_header_count, &coefs, &bounds);
 			if (log->level & BPF_LOG_LEVEL2) {
 				bpf_log(log, "loop header at %d, widening ", insn_idx);
 				log_reg(env, r);
 				bpf_log(log, " to ");
-				bpf_verbose_snum(env, cnum64_smin(bounds.range));
-				bpf_log(log, "..");
-				bpf_verbose_snum(env, cnum64_smax(bounds.range));
-				bpf_log(log, " step %u\n", bounds.step);
+				log_bounds(env, &bounds);
+				bpf_log(log, "\n");
 			}
 			scratch_widened_reg_id(env, reg);
-			err = bpf_set_reg_range(env, reg, bounds.range, bounds.base, bounds.step);
+			err = bpf_set_reg_range(env, reg, bounds.r64, bounds.r32,
+						bounds.base, bounds.step);
 			if (err)
 				return err;
 			mark_scev_reg_scratched(env, r);
@@ -2712,10 +2866,10 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur
 	struct bpf_verifier_log *log = &env->log;
 	struct bpf_reg_state *reg, *entry_reg;
 	struct scev *scev = env->scev;
+	struct linear_coefs coefs;
 	struct env *header_env;
 	struct bounds bounds;
-	u32 r, base_reg;
-	s64 slope_imm;
+	u32 r;
 	int err;
 
 	if (entry_state->curframe != cur_func_state->frameno) {
@@ -2727,8 +2881,8 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur
 	header_env = find_header_env(scev, insn_idx);
 	for (r = 0; r < REGS_NUM; r++) {
 		/* If SCEV for r is (linear <reg> <slope>)*/
-		if (!is_simple_linear(scev, header_env->reg2scev[r], &base_reg, &slope_imm) ||
-		    base_reg != r)
+		if (!is_simple_linear(scev, header_env->reg2scev[r], &coefs) ||
+		    coefs.base_reg != r)
 			continue;
 
 		entry_reg = scev_reg_for_linear(entry_st, r);
@@ -2737,9 +2891,10 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur
 		    is_unbound_scev_reg(env, entry_st, r))
 			continue;
 
-		linear_bounds(entry_reg, max_header_count, slope_imm, &bounds);
-		bounds.range = cnum64_intersect(reg->r64, bounds.range);
-		if (cnum64_is_empty(bounds.range)) {
+		linear_bounds(entry_reg, max_header_count, &coefs, &bounds);
+		bounds.r64 = cnum64_intersect(reg->r64, bounds.r64);
+		bounds.r32 = cnum32_intersect(reg->r32, bounds.r32);
+		if (cnum64_is_empty(bounds.r64)) {
 			verifier_bug(env, "scev clamp produced empty range for r%d", r);
 			return -EFAULT;
 		}
@@ -2747,13 +2902,12 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur
 			bpf_log(log, "loop header at %d, clamping ", insn_idx);
 			log_reg(env, r);
 			bpf_log(log, " to ");
-			bpf_verbose_snum(env, cnum64_smin(bounds.range));
-			bpf_log(log, "..");
-			bpf_verbose_snum(env, cnum64_smax(bounds.range));
-			bpf_log(log, " step %u\n", bounds.step);
+			log_bounds(env, &bounds);
+			bpf_log(log, "\n");
 		}
 		scratch_widened_reg_id(env, reg);
-		err = bpf_set_reg_range(env, reg, bounds.range, bounds.base, bounds.step);
+		err = bpf_set_reg_range(env, reg, bounds.r64, bounds.r32,
+					bounds.base, bounds.step);
 		if (err)
 			return err;
 		mark_scev_reg_scratched(env, r);
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e387320e196f..7d7193b087f6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -17716,10 +17716,10 @@ bool bpf_same_memory_origin(const struct bpf_reg_state *reg_a,
 }
 
 int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
-		      struct cnum64 range, u16 base, u16 step)
+		      struct cnum64 r64, struct cnum32 r32, u16 base, u16 step)
 {
-	reg->r64 = range;
-	reg->r32 = CNUM32_UNBOUNDED;
+	reg->r64 = r64;
+	reg->r32 = r32;
 	reg->step = step;
 	reg->base = base;
 	reg->var_off = tnum_unknown;