1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
/*
* Determines range (the min/max value) of integral expressions.
*
* Copyright © 2025 Samuel Lidén Borell <samuel@kodafritt.se>
*
* SPDX-License-Identifier: EUPL-1.2+ OR LGPL-2.1-or-later
*/
#include <assert.h>
#include "compiler.h"
bool is_const(const struct Range *range)
{
return range->min == range->max;
}
static SlulInt checked_add(SlulInt a, SlulInt b)
{
SlulInt x = a + b;
if (x < a) {
error("Addition might overflow");
}
return x;
}
static SlulInt checked_sub(SlulInt a, SlulInt b)
{
if (b > a) {
error("Subtraction might underflow");
}
return a - b;
}
static SlulInt checked_mul(SlulInt a, SlulInt b)
{
SlulInt x;
x = a * b;
if (b != 0 && x/b != a) {
error("Multiplication might overflow");
}
return x;
}
/** Computes minimum and maximum bounds of a modulus operations.
Takes some common cases into account, but not all. */
static struct Range range_mod(
const struct Range *a, const struct Range *b)
{
/* The range is never larger than 0..(b-1) */
struct Range r;
r.min = 0;
r.max = b->max - 1;
/* If `abs(a) < b`, then we can narrow down the range further */
if (is_const(b) &&
a->min < b->max && a->max < b->max) {
r.min = a->min;
r.max = a->max;
}
return r;
}
static void widen_range(
struct Range *r,
SlulInt n)
{
if (n < r->min) {
r->min = n;
}
if (n > r->max) {
r->max = n;
}
}
static struct Range sort_nums(
SlulInt a,
SlulInt b,
SlulInt c,
SlulInt d)
{
struct Range r = { SLUL_INT_MAX, 0 };
widen_range(&r, a);
widen_range(&r, b);
widen_range(&r, c);
widen_range(&r, d);
return r;
}
struct Range arithmetic_op_range(
enum ExprKind operation,
const struct Range *a,
const struct Range *b)
{
struct Range r;
switch ((int)operation) {
case E_ADD:
r.min = checked_add(a->min, b->min);
r.max = checked_add(a->max, b->max);
break;
case E_SUB:
r.min = checked_sub(a->min, b->max);
r.max = checked_sub(a->max, b->min);
break;
case E_MUL: {
SlulInt ll, lh, hl, hh;
ll = checked_mul(a->min, b->min);
lh = checked_mul(a->min, b->max);
hl = checked_mul(a->max, b->min);
hh = checked_mul(a->max, b->max);
r = sort_nums(ll, lh, hl, hh);
break; }
case E_DIV: {
SlulInt ll, lh, hl, hh;
if (b->min == 0) {
error("Possibility of division by zero");
}
ll = a->min / b->min;
lh = a->min / b->max;
hl = a->max / b->min;
hh = a->max / b->max;
r = sort_nums(ll, lh, hl, hh);
break; }
case E_MOD:
/* `b` must be positive
(the bootstrap compiler doens't support negative numbers,
so a check for zero is sufficient here) */
if (b->min == 0) {
error("Possibility of modulus by zero");
}
assert(b->max != 0);
if (is_const(a) && is_const(b)) {
r.min = r.max = a->min % b->min;
} else if (is_const(a) && a->min == 0) {
r.min = r.max = 0;
} else {
r = range_mod(a, b);
}
break;
default: unreachable();
}
return r;
}
|
