20250330

CFG in SSA form

A CFG in SSA form is a representation where each variable is assigned a value only once within the CFG, and each use of a variable refers to the most recent definition, ensuring simpler analysis and optimization.

CFG: control flow graph SSA: static single assignment

A CFG is a graph that represents the control flow of a program. Nodes in the CFG represent basic blocks (sequences of instructions that execute sequentially without branches), and edges represent the possible execution paths between those blocks.

SSA form is a way to represent code where each variable is assigned a value only once within the program’s execution path. This means that each time a variable is assigned a new value, it’s given a new name. This makes it easier for compilers to perform certain optimizations, such as dead code elimination and common subexpression elimination.

To achieve SSA form, compilers often insert special instructions called phi-functions at the join points of the CFG where control flow merges from different paths. Phi-functions select the appropriate value of a variable based on which path was taken to reach that point.

Consider the following example code snippet:

if (condition) {
  x = 1;
} else {
  x = 2;
}
y = x + 3;

In SSA form, the code might look as follows:

if (condition) {
  x1 = 1;
} else {
  x2 = 2;
}

x3 = phi(x1, x2); // phi function to select the correct value of x
y = x3 + 3;

reference

• Harvard CS153: Lecture23 SSA form by Stephen Chong

• SSA form

• lab: SSA form

• Cornell Global Analysis and SSA form

• IR by Cliff click

code async and await

Tags vs function calls Nouns are timeless, while verbs describe processes which happen over time. Verbs are timeful because actions are only exit and disappear in the time.

Recipe (imperative program) vs blueprint (parts and the whole, declarative)

When the function calls happen within one program, the execution of the call is almost immediate. However, when the function calls happen between two computers, the execution has to depend on the other machine. For example, we might wait for the response from the other computer or process. An HTTP call is bit different from a function call.

Async: an asynch function is not guaranteed to execute in a single step. Rather it is expected that it may “pause” the execution (for example due to network calls).

RPC: remote procedure call

Now what if the other end won’t or not able to respond?

alert<
  concat<
    'Hello, ',
    prompt<'Who are you?'>
  >
>;

the above pseudo code could be translate into the following JSON code and sent over the network.

{
  fn: 'alert',
  args: [{
    fn: 'concat',
    args: ['Hello, ', {
      fn: 'prompt',
      args: ['Who are you?']
    }]
  }]
}

the above JSON code could be tranlated into the following code at the remote computer.

function interpret(json) {
  if (json && json.fn) {
    // Find a global function by its name
    let fn = window[json.fn];
    // Interpret any nested potential calls in the arguments
    let args = json.args.map(arg => interpret(arg));
    // Actually perform the call now
    let result = fn(...args);
    // If it returned more potential calls, do them next
    return interpret(result);
  } else {
    return json;
  }
}

with a regular function call, the return value is decided by the function called. However, for a “potential” function call, the return value is the call itself as data.

Here is the regular function:

function greeting() {
  const name = prompt('Who are you?');
  alert('Hello, ' + name);
}

Here is the “potential” function:

function greeting() {
  const name = prompt('Who are you?');
  return function resume() {
    alert('Hello, ' + name);
  };
}

• react for two computers