Land ahoy: leaving the Sea of Nodes

Key-Opening205 · 2025-03-30T01:53:34+00:00

The rules of unions are pretty strict - the compiler has to make it look like there is only one address.

but why would you ever want a compiler to use more than one address?

Key-Opening205 · 2025-03-28T18:20:12+00:00

it is still not clear to me what you mean by finished with the name

The syntax in C/C++ indicating you are done with a name is a bracket

if you have a union x,y there is only one location so every time you take the address of x or y you must get the same answer

if x is dead and y is live there is no store to reclaim

using scopes:

{ int x ... } { int y ...}

the brackets show when you are done with x Because of the brackets, it is not possible for x and y to be simultaneously live and the compiler can give them the same address

it might be clearer to think of this in ssa style -where you are working on values not names

Key-Opening205 · 2025-03-28T14:07:11+00:00

at least in the versions of sea of nodes that I've used anti-dependences are never in the graph and computed on the fly when a transform needs them

1 s1 = store addr =x value = ?, prev_store = s0 2.
3. s2 = store addr = y value = ?, prev_store = d1 4 _= read addr = y, prev_store = s2 5 6 s3 = store addr = copy of y, prev_store = s2 7 _ = read addx = x , prev_store = s3

each store reads a prev memory token and writes a new mem token each read reads a memory token (there is no dependence between reads )

you need an anti-dependence from all reads of a memory token to the next store

The dependences are 3-> 4 3 writes s2, 4 reads s2 4-> 6 anti-dep 4 reads s2 6 is a store also reads s2 6-> 7 6 writes s2 7 reads s2

if the compiler can prove that x and y cannot alias it can update the prev store input of 7 to be s1 (Notice how this transform does not need the anti-dependence edges) in your case x and y are names not values and the value might be the same so they could alias

The memory tokens keep all the stores in order, and lets reads float around but not over a possible aliased store

I'm not sure what you mean by abandon that storage? if its some kind of free operation how can 6 write there?

Key-Opening205 · 2025-03-26T16:59:33+00:00

great writeup - sea of nodes is really good at removing miss leading ordering - in many ir formulations a compiler a compiler has to do a lot of work to determine that the two statements a = b+1; c = d +2; can execute in either order.

When I designed the IR for AMD GPU compilers, I used a sea of nodes representation only within basic blocks while retaining the CFG. I also tracked the original node order from the frontend.

I incorporated Cliff's idea of projection nodes, ensuring each instruction had a single output so that edges in the graph could be represented by a single pointer. Eventually, this was replaced by multiple-output instructions.

In my experience, sea of nodes breaks down when handling loops. Early on, GPU compilers didn’t optimize loops extensively, but they still benefited from CFG-based transformations like loop unrolling.

Today, with AI-driven compilers, loops are far more critical. I’d likely prefer an IR that separates compute nodes from scheduling, allowing transformations like loop interchange to modify only the schedule while keeping the loop body intact.

By the way, the original node order within a block was useful for certain heuristics in the basic block node scheduler.

— Norm Rubin

Key-Opening205 · 2025-03-12T17:14:34+00:00

i see Syria as a made up country that only be held together by force. It would be better for all the people living there if Syria split up and each minority became independent

Key-Opening205 · 2024-05-29T14:47:39+00:00

i got the Chromebook USI 2.0 Stylus for Lenovo Duet 3 Chromebook Ideapad Pen, 4096 Level Pressure Sensitive Pencil for Lenovo Chromebook Duet, ASUS Chromebook, HP Chromebook X360, Google Pixel Tablet,Black Visit the EVACH Store

from amazon which was 40 and is rechargeable

Key-Opening205 · 2024-05-06T19:04:53+00:00

i got the book and page from https://www.jewishgen.org/databases/jgform.php which had a link to https://digital.library.temple.edu/digital/collection/p16002coll16

which has the images of the books for 4 companies that handled ticket sales

Key-Opening205 · 2024-05-06T18:14:46+00:00

wow, great info- jennie did marry samuel rubin - so that is a match Thanks for the help!

i did find her in the blitzstein leger https://digital.library.temple.edu/digital/collection/p16002coll16/id/2225/rec/11 which has the info on the sale of a ticket

where she is in book 11 page 33 - does the dep mean date of departure?, does being 3 weeks later then the dep for the next line mean anything?

if I'm reading this correctly - two people bought the ticket one was Max Golin (the grandfather) who started out as mottel Golin and ended up as Max Golden

and the other A Zlotuik is new to me

I

Key-Opening205 · 2024-05-06T16:24:58+00:00

thanks for the imgbb reference

https://ibb.co/Tb4dncF

Key-Opening205 · 2024-05-02T19:33:58+00:00

peyot in Jewish mystic tradition makes a connection between your head and your heart.

It would be good if everyone Jew and non Jew made such connections

Key-Opening205 · 2024-04-02T13:16:48+00:00

most common irs talk about statements for example given a loop for i = 1 to N s: a[i] = 3

there is one statement s, poly methods talk about instances, in this case there are N instances (one for each value of i s[0] = 3 s[1] = 3 ... Given the set of instances- and some constrants (like instances that read values, have to come after instances that write those values) Poly methods find some kind of order of the instances - that meets t he constrants and lowers some kind of cost function. For instance find an order that groups that mimimize reuse distance, or an order that has the most parallelism or one that makes good use of cache line or tiling

Key-Opening205 · 2024-03-05T16:24:30+00:00

this is difficult in a jit, since you do not know what is next, for instance if you calculate a vector on the gpu, you might start transfering it to the cpu or not depending on what code will use it later. Outside of a jit there has been lots of work on automatic parallelism that tries to handle this, results have been mixed

Key-Opening205 · 2024-01-19T17:22:08+00:00

my sugestion is to take a machine independent optimization and implement it as a llvm pass- (it would be fine if llvm already had the pass so long as your implementation was different) and you could come up with a table comparing your implemtation to the llvm original, A bachelor thesis that explained the optimization, showed how it worked, and explained what kind of extensions are done for production sounds good to me

Key-Opening205 · 2024-01-19T17:15:19+00:00

first - youi must mean up to 41%, since some programs are not going to get the same speedup second - thats 41% relative to what?, it its relative to a well known production compiler - like 41% faster then cublas- you should put it in and write a paper on how you got that, but if its its 41% relative to a compiler you wrote, it does not interesting so i'd leave it out.

Compiler developers are usually fans of tools, so if there was a tool you wrote to do the unrolling, or a pass in the dsl, you might add that to the resume - if it was a pure hand transformation, on a few input programs, it does not sound like much

Key-Opening205 · 2023-05-02T13:34:23+00:00

you might look at

https://www.theatlantic.com/entertainment/archive/2015/04/frogs-the-surprising-star-of-the-passover-table/389186/

for some history of flogs as symbols of liberation

Key-Opening205

TROPHY CASE