14template<
class Id, Id
id, nat_t w>
15Res fold(
u64 a,
u64 b, [[maybe_unused]]
bool nsw, [[maybe_unused]]
bool nuw) {
18 auto s = thorin::bitcast<ST>(
a),
t = thorin::bitcast<ST>(b);
19 auto u = thorin::bitcast<UT>(
a), v = thorin::bitcast<UT>(b);
21 if constexpr (std::is_same_v<Id, wrap>) {
24 if (
nuw && res <
u)
return {};
32 if constexpr (std::is_same_v<UT, bool>)
37 if (b >= w)
return {};
39 if constexpr (std::is_same_v<UT, bool>)
43 if (
nuw && res <
u)
return {};
47 []<
bool flag =
false>() {
static_assert(flag,
"missing sub tag"); }();
49 }
else if constexpr (std::is_same_v<Id, shr>) {
50 if (b >= w)
return {};
51 if constexpr (
false) {}
52 else if constexpr (
id ==
shr::a)
return s >>
t;
53 else if constexpr (
id ==
shr::l)
return u >> v;
54 else []<
bool flag =
false>() {
static_assert(flag,
"missing sub tag"); }();
55 }
else if constexpr (std::is_same_v<Id, div>) {
56 if (b == 0)
return {};
57 if constexpr (
false) {}
59 else if constexpr (
id ==
div::udiv)
return u / v;
61 else if constexpr (
id ==
div::urem)
return u % v;
62 else []<
bool flag =
false>() {
static_assert(flag,
"missing sub tag"); }();
63 }
else if constexpr (std::is_same_v<Id, icmp>) {
65 auto pm = !(
u >> UT(w - 1)) && (v >> UT(w - 1));
66 auto mp = (
u >> UT(w - 1)) && !(v >> UT(w - 1));
73 }
else if constexpr (std::is_same_v<Id, extrema>) {
74 if constexpr (
false) {}
80 []<
bool flag =
false>() {
static_assert(flag,
"missing tag"); }();
86template<
class Id, Id
id> Ref fold(World& world, Ref type,
const Def*&
a,
const Def*& b, Ref
mode = {}) {
87 if (
a->isa<
Bot>() || b->isa<
Bot>())
return world.bot(type);
93 bool nsw =
false,
nuw =
false;
94 if constexpr (std::is_same_v<Id, wrap>) {
103 case i: res = fold<Id, id, i>(*la, *lb, nsw, nuw); break;
108 res = fold<Id, id, 64>(*la, *lb,
false,
false);
109 if (res && !std::is_same_v<Id, icmp>) *res %=
size;
112 return res ? world.lit(type, *res) : world.bot(type);
120template<
class Id, nat_t w> Res fold(
u64 a, [[maybe_unused]]
bool nsw, [[maybe_unused]]
bool nuw) {
122 auto s = thorin::bitcast<ST>(
a);
124 if constexpr (std::is_same_v<Id, abs>) {
127 []<
bool flag =
false>() {
static_assert(flag,
"missing tag"); }
132template<
class Id> Ref fold(World& world, Ref type,
const Def*&
a) {
133 if (
a->isa<
Bot>())
return world.bot(type);
138 bool nsw =
false,
nuw =
false;
142 case i: res = fold<Id, i>(*la, nsw, nuw); break;
146 res = fold<Id, 64>(*la,
false,
false);
147 if (res && !std::is_same_v<Id, icmp>) *res %=
size;
150 return res ? world.lit(type, *res) : world.bot(type);
166template<
class Id> Ref reassociate(Id
id, World& world, [[maybe_unused]]
const App* ab, Ref
a, Ref b) {
169 auto xy = match<Id>(
id,
a);
170 auto zw = match<Id>(
id, b);
171 auto la =
a->isa<
Lit>();
172 auto [x, y] = xy ? xy->template args<2>() :
std::array<const Def*, 2>{
nullptr,
nullptr};
173 auto [z,
w] = zw ? zw->template args<2>() :
std::array<const Def*, 2>{
nullptr,
nullptr};
178 auto make_op = [&world,
id](Ref
a, Ref b) {
return world.call(
id,
Mode::none,
Defs{
a, b}); };
180 if (la && lz)
return make_op(make_op(
a, z), w);
181 if (lx && lz)
return make_op(make_op(x, z), make_op(y, w));
182 if (lz)
return make_op(z, make_op(
a, w));
183 if (lx)
return make_op(x, make_op(y, b));
187template<
class Id> Ref merge_cmps(std::array<std::array<u64, 2>, 2> tab, Ref
a, Ref b) {
188 static_assert(
sizeof(
sub_t) == 1,
"if this ever changes, please adjust the logic below");
189 static constexpr size_t num_bits = std::bit_width(
Annex::Num<Id> - 1_u64);
191 auto& world =
a->world();
192 auto a_cmp = match<Id>(
a);
193 auto b_cmp = match<Id>(b);
195 if (a_cmp && b_cmp && a_cmp->arg() == b_cmp->arg()) {
198 sub_t a_sub = a_cmp.sub();
199 sub_t b_sub = b_cmp.sub();
200 for (
size_t i = 0; i != num_bits; ++i, res >>= 1, a_sub >>= 1, b_sub >>= 1)
201 res |= tab[a_sub & 1][b_sub & 1] << 7_u8;
202 res >>= (7_u8 -
u8(num_bits));
204 if constexpr (std::is_same_v<Id, math::cmp>)
205 return world.call(
math::cmp(res), a_cmp->decurry()->arg(), a_cmp->arg());
216 auto& world = type->
world();
217 auto [
a, b] = arg->
projs<2>();
225 case nat::add:
return world.lit_nat(*la + *lb);
226 case nat::sub:
return *la < *lb ? world.lit_nat_0() : world.lit_nat(*la - *lb);
227 case nat::mul:
return world.lit_nat(*la * *lb);
233 case nat::add:
return b;
234 case nat::sub:
return a;
235 case nat::mul:
return a;
239 if (*la == 1 &&
id == nat::mul)
return b;
242 if (lb && *lb == 0 &&
id == nat::sub)
return a;
244 return world.raw_app(type, callee, {
a, b});
248 auto& world = type->
world();
250 if (
id == ncmp::t)
return world.
lit_tt();
251 if (
id == ncmp::f)
return world.lit_ff();
253 auto [
a, b] = arg->
projs<2>();
260 case ncmp:: e:
return world.lit_nat(*la == *lb);
261 case ncmp::ne:
return world.lit_nat(*la != *lb);
262 case ncmp::l :
return world.lit_nat(*la < *lb);
263 case ncmp::le:
return world.lit_nat(*la <= *lb);
264 case ncmp::g :
return world.lit_nat(*la > *lb);
265 case ncmp::ge:
return world.lit_nat(*la >= *lb);
266 default: fe::unreachable();
272 return world.raw_app(type, callee, {
a, b});
276 auto& world = type->
world();
277 auto callee = c->as<
App>();
278 auto [
a, b] = arg->
projs<2>();
280 if (
auto result = fold<icmp, id>(world, type,
a, b))
return result;
281 if (
id ==
icmp::f)
return world.lit_ff();
282 if (
id ==
icmp::t)
return world.lit_tt();
284 if (
id & (
icmp::e & 0xff))
return world.lit_tt();
285 if (
id ==
icmp::ne)
return world.lit_ff();
288 return world.raw_app(type, callee, {
a, b});
292 auto& world = type->
world();
293 auto callee = c->as<
App>();
294 auto [
a, b] = arg->
projs<2>();
295 if (
auto result = fold<extrema, id>(world, type,
a, b))
return result;
296 return world.raw_app(type, callee, {
a, b});
300 auto& world = type->
world();
301 auto callee = c->as<
App>();
303 auto [_, actual_type] = type->
projs<2>();
304 auto make_res = [&,
mem =
mem](
Ref res) {
return world.tuple({
mem, res}); };
306 if (
auto result = fold<abs>(world, actual_type,
a))
return make_res(result);
307 return world.raw_app(type, callee, arg);
311 auto& world = type->
world();
312 auto callee = c->as<
App>();
320 case bit1::f:
return world.lit_idx(*ls, 0);
321 case bit1::t:
return world.lit_idx(*ls, *ls - 1_u64);
327 if (
auto la =
Lit::isa(
a))
return world.lit_idx_mod(*ls, ~*la);
330 return world.raw_app(type, callee,
a);
334 auto& world = type->
world();
335 auto callee = c->as<
App>();
336 auto [
a, b] = arg->
projs<2>();
337 auto s = callee->decurry()->arg();
344 if (
auto res = merge_cmps<icmp>(tab,
a, b))
return res;
345 if (
auto res = merge_cmps<math::cmp>(tab,
a, b))
return res;
352 case bit2:: f:
return world.lit(type, 0);
353 case bit2:: t:
if (ls)
return world.lit(type, *ls-1_u64);
break;
363 if (la && lb && ls) {
365 case bit2::and_:
return world.lit_idx (*ls, *la & *lb);
366 case bit2:: or_:
return world.lit_idx (*ls, *la | *lb);
367 case bit2::xor_:
return world.lit_idx (*ls, *la ^ *lb);
368 case bit2::nand:
return world.lit_idx_mod(*ls, ~(*la & *lb));
369 case bit2:: nor:
return world.lit_idx_mod(*ls, ~(*la | *lb));
370 case bit2::nxor:
return world.lit_idx_mod(*ls, ~(*la ^ *lb));
371 case bit2:: iff:
return world.lit_idx_mod(*ls, ~ *la | *lb);
372 case bit2::niff:
return world.lit_idx (*ls, *la & ~*lb);
373 default: fe::unreachable();
378 auto unary = [&](
bool x,
bool y,
Ref a) ->
Ref {
379 if (!x && !y)
return world.lit(type, 0);
380 if ( x && y)
return ls ? world.lit(type, *ls-1_u64) :
nullptr;
381 if (!x && y)
return a;
388 if (
auto res = unary(tab[0][0], tab[1][1],
a))
return res;
393 if (
auto res = unary(tab[0][0], tab[0][1], b))
return res;
394 }
else if (ls && *la == *ls - 1_u64) {
395 if (
auto res = unary(tab[1][0], tab[1][1], b))
return res;
401 if (
auto res = unary(tab[0][0], tab[1][0],
a))
return res;
402 }
else if (ls && *lb == *ls - 1_u64) {
403 if (
auto res = unary(tab[0][1], tab[1][1],
a))
return res;
407 if (
auto res = reassociate<bit2>(
id, world, callee,
a, b))
return res;
409 return world.raw_app(type, callee, {
a, b});
413 auto& world = type->
world();
414 auto callee = c->as<
App>();
417 if (*i < *
s)
return world.lit_idx(*
s, *i);
418 if (
auto m =
Lit::isa(callee->arg()))
return *m ? world.bot(type) : world.lit_idx_mod(*
s, *i);
422 return world.raw_app(type, c, arg);
426 auto& world = type->
world();
427 auto callee = c->as<
App>();
428 auto [
a, b] = arg->
projs<2>();
432 if (
auto result = fold<shr, id>(world, type,
a, b))
return result;
434 if (
auto la =
Lit::isa(
a); la && *la == 0) {
442 if (ls && *lb > *ls)
return world.bot(type);
452 return world.raw_app(type, callee, {
a, b});
456 auto& world = type->
world();
457 auto callee = c->as<
App>();
458 auto [
a, b] = arg->
projs<2>();
459 auto mode = callee->arg();
463 if (
auto result = fold<wrap, id>(world, type,
a, b))
return result;
474 }
else if (*la == 1) {
489 default: fe::unreachable();
495 return world.call(
wrap::add,
mode,
Defs{a, world.lit_idx_mod(*ls, ~*lb + 1_u64)});
496 else if (
id ==
wrap::shl && ls && *lb > *ls)
497 return world.bot(type);
503 case wrap::sub:
return world.lit(type, 0);
510 if (
auto res = reassociate<wrap>(
id, world, callee,
a, b))
return res;
512 return world.raw_app(type, callee, {
a, b});
516 auto& world = full_type->
world();
517 auto callee = c->as<
App>();
519 auto [
a, b] = ab->projs<2>();
520 auto [_, type] = full_type->
projs<2>();
521 auto make_res = [&,
mem =
mem](
Ref res) {
return world.tuple({
mem, res}); };
523 if (
auto result = fold<div, id>(world, type,
a, b))
return make_res(result);
526 if (*la == 0)
return make_res(
a);
530 if (*lb == 0)
return make_res(world.bot(type));
536 case div::srem:
return make_res(world.lit(type, 0));
537 case div::urem:
return make_res(world.lit(type, 0));
544 case div::sdiv:
return make_res(world.lit(type, 1));
545 case div::udiv:
return make_res(world.lit(type, 1));
546 case div::srem:
return make_res(world.lit(type, 0));
547 case div::urem:
return make_res(world.lit(type, 0));
551 return world.raw_app(full_type, callee, arg);
555 auto& world = dst_t->
world();
556 auto callee = c->as<
App>();
557 auto s_t = x->
type()->as<
App>();
558 auto d_t = dst_t->as<
App>();
564 if (s_t == d_t)
return x;
565 if (x->isa<
Bot>())
return world.bot(d_t);
567 if (ls && ld && *ld < *ls)
return world.call(
conv::u, d, x);
572 if (*ld == 0)
return world.lit(d_t, *
l);
573 return world.lit(d_t, *
l % *ld);
582 else if (S == sw && D == dw) return world.lit(d_t, w2s<D>(thorin::bitcast<w2s<S>>(*l)));
583 M( 1, 8)
M( 1, 16)
M( 1, 32)
M( 1, 64)
584 M( 8, 16)
M( 8, 32)
M( 8, 64)
587 else assert(
false &&
"TODO: conversion between different Idx sizes");
591 return world.raw_app(dst_t, callee, x);
595 auto& world = dst_t->
world();
596 auto src_t = src->
type();
598 if (src->isa<
Bot>())
return world.bot(dst_t);
599 if (src_t == dst_t)
return src;
601 if (
auto other = match<bitcast>(src))
602 return other->arg()->
type() == dst_t ? other->arg() : world.call<
bitcast>(dst_t, other->arg());
605 if (dst_t->isa<
Nat>())
return world.lit(dst_t, *
l);
606 if (
Idx::size(dst_t))
return world.lit(dst_t, *
l);
609 return world.raw_app(dst_t, callee, src);
617 auto& world = type->
world();
618 if (
auto ptr = match<mem::Ptr>(type)) {
620 }
else if (type->isa<
Pi>()) {
621 return world.lit_nat(8);
626 case 16:
return world.lit_nat(2);
627 case 32:
return world.lit_nat(4);
628 case 64:
return world.lit_nat(8);
629 default: fe::unreachable();
631 }
else if (type->isa<
Sigma>() || type->isa<
Meet>()) {
634 for (
auto t : type->
ops()) {
637 if (!
a || !
s)
goto out;
640 offset =
pad(offset, *
a) + *
s;
644 u64 size = std::max(1_u64, offset);
654 if (b->isa<
Lit>())
return world.call(nat::mul,
Defs{arr->shape(), b});
655 }
else if (
auto join = type->isa<
Join>()) {
660 return world.raw_app(
nat, callee, type);
664 auto& w = type->
world();
665 auto callee = c->as<
App>();
666 auto is_os = callee->
arg();
667 auto [n_i, Is, n_o, Os,
f] = is_os->
projs<5>();
668 auto [r,
s] = callee->decurry()->args<2>();
677 if (lr && ls && *lr == 1 && *ls == 1)
return w.app(
f, arg);
680 auto args = arg->
projs(*l_in);
682 if (lr && std::ranges::all_of(args, [](
Ref arg) {
return arg->isa<
Tuple,
Pack>(); })) {
683 auto shapes =
s->projs(*lr);
684 auto s_n =
Lit::isa(shapes.front());
687 auto elems =
DefVec(*s_n, [&,
f =
f](
size_t s_i) {
688 auto inner_args =
DefVec(args.size(), [&](
size_t i) { return args[i]->proj(*s_n, s_i); });
690 return w.app(
f, inner_args);
692 auto app_zip = w.app(w.annex<
zip>(), {w.lit_nat(*lr - 1), w.tuple(shapes.view().subspan(1))});
693 return w.app(w.app(app_zip, is_os), inner_args);
696 return w.tuple(elems);
701 return w.raw_app(type, callee, arg);
705 auto& world = type->
world();
709 if (arg->
dep_const())
return world.lit_tt();
712 return world.raw_app(type, callee, arg);
const App * decurry() const
Returns App::callee again as App.
A (possibly paramterized) Array.
auto projs(F f) const
Splits this Def via Def::projections into an Array (if A == -1_n) or std::array (otherwise).
const T * isa_imm() const
const Def * type() const
Yields the raw type of this Def, i.e. maybe nullptr.
static Ref size(Ref def)
Checks if def is a .Idx s and returns s or nullptr otherwise.
static constexpr nat_t size2bitwidth(nat_t n)
static std::optional< T > isa(Ref def)
A (possibly paramterized) Tuple.
A dependent function type.
Helper class to retrieve Infer::arg if present.
This is a thin wrapper for std::span<T, N> with the following additional features:
Specific Bound depending on Up.
Extremum. Either Top (Up) or Bottom.
Data constructor for a Sigma.
const Lit * lit_nat(nat_t a)
#define THORIN_core_NORMALIZER_IMPL
Ref normalize_ncmp(Ref type, Ref callee, Ref arg)
Ref normalize_icmp(Ref type, Ref c, Ref arg)
Ref normalize_bit1(Ref type, Ref c, Ref a)
Ref normalize_extrema(Ref type, Ref c, Ref arg)
constexpr std::array< std::array< u64, 2 >, 2 > make_truth_table(bit2 id)
Use like this: a op b = tab[a][b]
Ref normalize_bit2(Ref type, Ref c, Ref arg)
Ref normalize_zip(Ref type, Ref c, Ref arg)
@ nuw
No Unsigned Wrap around.
@ nsw
No Signed Wrap around.
Ref normalize_nat(Ref type, Ref callee, Ref arg)
Ref op(trait o, Ref type)
Ref normalize_div(Ref full_type, Ref c, Ref arg)
Ref normalize_idx(Ref type, Ref c, Ref arg)
Ref normalize_trait(Ref nat, Ref callee, Ref type)
Ref normalize_conv(Ref dst_t, Ref c, Ref x)
Ref normalize_abs(Ref type, Ref c, Ref arg)
Ref normalize_wrap(Ref type, Ref c, Ref arg)
Ref normalize_shr(Ref type, Ref c, Ref arg)
Ref normalize_pe(Ref type, Ref callee, Ref arg)
Ref normalize_bitcast(Ref dst_t, Ref callee, Ref src)
const Sigma * convert(const TBound< up > *b)
std::optional< nat_t > isa_f(Ref def)
constexpr bool is_associative(Id id)
void commute(const Def *&a, const Def *&b)
Swap Lit to left - or smaller Def::gid, if no lit present.
u64 pad(u64 offset, u64 align)
constexpr bool is_commutative(Id)
Vector< const Def * > DefVec
static constexpr flags_t Base
#define THORIN_1_8_16_32_64(m)