Document refine_coordinate

[yuanming-hu]

Per the request in #593

[k-ye]

Actually, I think I figured out what has confused me. I hope my example could help explain the process:

x = ti.var(ti.i32)
ti.root.dense(ti.i, 4).bitmasked().dense(ti.i, 8).place(x)

@ti.kernel
def foo():
  for i in x:
    x[i] = 42

foo()

Here's the relevant fields for each SNode of its index 0:

snode	size	num_bits	mask	acc_offset	start
S0	1	1	0x1	0	5
S1	4	2	0x3	0	3
S2	8	3	0x7	0	0

For a concrete example where the input linear index l=17, if I'm following the flow correctly:

taichi/taichi/struct/struct_llvm.cpp

Lines 110 to 122 in 6577ad3

	auto addition = tlctx->get_constant(0);
	if (snode->extractors[i].num_bits) {
	auto mask = ((1 << snode->extractors[i].num_bits) - 1);
	addition = builder.CreateAnd(
	builder.CreateAShr(l, snode->extractors[i].acc_offset), mask);
	addition = builder.CreateShl(
	addition, tlctx->get_constant(snode->extractors[i].start));
	}
	auto in = call(&builder, "PhysicalCoordinates_get_val", inp_coords,
	tlctx->get_constant(i));
	auto added = builder.CreateOr(in, addition);
	call(&builder, "PhysicalCoordinates_set_val", outp_coords,
	tlctx->get_constant(i), added);

Then during element_listgen(), this should be its intermediate results

snode	l	addition	in	out
S0	0	((l >> 0) & 0x1) << 5 = 0	0	0 or 0 = 0
S1	2	((l >> 0) & 0x3) << 3 = 16	2	2 or 16 = 16
S2	1	((l >> 0) & 0x7) << 0 = 1	16	16 or 1 = 17

What I went wrong before was that, in each parent -> child listgen, I used the same l = 17. As a result, the final output I got was 41 instead of 17...

[yuanming-hu]

I think your understanding now is mostly correct, excapt for a few numbers in the table, updated below:

snode	size	num_bits	mask	acc_offset	start
S0_root	1	0	0x0	0	5
S1_dense	4	2	0x3	0	3
S2_dense	8	3	0x7	0	0

snode	l	addition	in	out
S0	0	((l >> 5) & 0x0) << 5 = 0	0	0 or 0 = 0
S1	2	((l >> 3) & 0x3) << 3 = 16	0	0 or 16 = 16
S2	1	((l >> 0) & 0x7) << 0 = 1	16	16 or 1 = 17

[k-ye]

btw, i believe they should all be ((l >> 0)... :)

[yuanming-hu]

btw, i believe they should all be ((l >> 0)... :)

Oh sorry. I didn't realize what l is in the second table (2nd column) so I assumed we are working on 17 throughout this process....

[k-ye]

Oh sorry. I didn't realize what l is in the second table (2nd column) so I assumed we are working on 17 throughout this process....

My bad, I meant to use 17 as the 17-th leaf element of x.

The l in the table is actually the third argument of the refine coordinates function:

taichi/taichi/struct/struct_llvm.cpp

Line 107 in 6577ad3

auto l = args[2];

[github-actions]

Warning: The issue has been out-of-update for 50 days, marking stale.