---
# System prepended metadata

title: Data-flow analysis (Constant Propagation)
tags: [ebpf]

---

###### tags: `ebpf`

# Data-flow analysis (Constant Propagation)

```
/*
language: 

stmt ::= var = val | var = val+val
val ::= const | var
*/

states : map<cfg_node, map<var, const>>;
```

```
// + is join operator
def operator+(state1, state2):
  state = map{};
  for (key, value) in state1:
    if key in state2 and value == state2[key]:
      state[key] = value;
  return state;
```

```
def join_at(bb):
  all_preds = cfg.get_all_predecessors(bb);
  for i in [0..all_preds.length()]:
    if i == 0:
      state = states[all_preds[i]]
    else:
      state = state+states[all_preds[i]];
  return state;
```

```
state = map{};

for bb in cfg.topological_sort():
  if cfg.num_of_processors(bb) == 1:
    state = states[cfg.get_predecessor(bb)];
  else if cfg.num_of_processors(bb) > 1:
    state = join_at(bb);
    
  for instr in bb:
    
    match(instr) with:
      a = b ->
        if b is var and b in state:
          state[a] = state[b];
        else if b is const:
          state[a] = b;
      
      a = b+c ->
        if b is var and c is var:
          if b in state and c in state:
            state[a] = state[b]+state[c];
        else if b is var:
          if b in state:
            state[a] = state[b]+c;
        else if c is var:
          if c in state:
            state[a] = state[c]+b;
        else:
          state[a] = b+c;
  
  states[bb] = state;    
```