<p>You can modify the tuple of control flow graph and data flow graph, or its hybrid control/data flow graph (CDFG), to generate a dependency graph.</p>
<p>You may even be able to generate this, while producing the CDFG for LLVM.</p>
<p>Memory access pattern classification into regular blocks and irregular blocks can also be done with dynamic/binary analysis at run time, instead of static program analysis.</p>
<p>Memory access pattern classification is also ISA/hardware dependent, so you would have to process the output of code generation (usually in binary, or assembly code).</p>

CC BY-SA 4.0
2024-10-17T11:38:34.200Z
2024-10-17T11:38:34.200Z
Giovanni
<p>I am currently encountering issues with using LLVM. Here is my specific problem:</p>
<p>I want to study the <strong>memory access patterns</strong> of applications that are suitable for mapping onto a <em>Spatial Accelerator</em>, such as FFT, AES, Convolution, and SpMV (Sparse Matrix Vector Multiply). The memory access patterns in the loops of these applications can generally be categorized into two types: one is <code>A[i]</code>, and the other is <code>A[B[i]]</code> (commonly found in sparse computations like SpMV or BFS or Btree Algorithm). The former is a regular stream access, while the latter is nested access with irregular dependency. <strong>Nested access has a dependency where the value from the previous access is needed as the address for the next access.</strong></p>
<p>I want to use LLVM to classify the data blocks of an application, <strong>distinguishing between regular and irregular data blocks</strong>, so that different hardware modules can be used to handle them separately to improve performance. The reason for using LLVM is that Spatial Accelerators typically use LLVM as the compiler frontend to convert source code to IR for backend mapping, which means this approach is widely applicable.</p>
<p>To classify the memory access behaviors of data blocks, my current idea is to <strong>first convert the source code to IR and record all Load/Store IR</strong>. Then, I plan to <strong>traverse backward for each load/store IR to find if the value obtained by a previous load is used as the address for the current load/store</strong>, as shown in the figure below. However, I find that if a brute-force search is used, it requires <em>O(N^2)</em> complexity, which might be criticized. I would like to ask if there is a smarter approach, or if my initial idea is fundamentally flawed? Thanks in advance for any help!</p>
<p><a href="https://i.sstatic.net/rUgcim4k.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/rUgcim4k.png" alt="An Example to Find Memory Access Dependency in x86 Architecture" /></a></p>

CC BY-SA 4.0
2024-05-26T16:07:15.517Z
iiuc, you want to construct the graph of explicit dependency between lines in a given assembly code. I think it should be possible to do so in linear time. Just keep the last line in which each of those dependency creating objects was updated.
Kaveh
CC BY-SA 4.0
2024-05-26T16:09:42.257Z
if you want to go beyond explicit synthetic depends, e.g. through memory locations or stack, I think they problem then becomes as hard as executing the program itself (because of jumps and loops and recursion and...).
Kaveh
CC BY-SA 4.0
2024-05-27T08:28:42.103Z
@Kaveh Thank you for your help. I am sorry that I might not fully understand your point. Are you suggesting that during a traversal of all the assembly code, we only need to record the last node of each dependency chain for comparison? E.g., if we have two dependency chains, A-B-C and D-E, when we reach node F, we only need to compare node F with nodes C or E to check for dependencies? However, is it possible that a middle node of a dependency chain might have a dependency with the current instruction being traversed?
Chris_Wu
<ds.algorithms><pl.programming-languages><program-analysis><memory>
How to Classify Memory Access Pattern by LLVM or Other Tools?
Chris_Wu
# How to Classify Memory Access Pattern by LLVM or Other Tools?

(Asked by: username_0 on 2024-05-26)

I am currently encountering issues with using LLVM. Here is my specific problem:

I want to study the **memory access patterns** of applications that are suitable for mapping onto a *Spatial Accelerator*, such as FFT, AES, Convolution, and SpMV (Sparse Matrix Vector Multiply). The memory access patterns in the loops of these applications can generally be categorized into two types: one is `A[i]`, and the other is `A[B[i]]` (commonly found in sparse computations like SpMV or BFS or Btree Algorithm). The former is a regular stream access, while the latter is nested access with irregular dependency. **Nested access has a dependency where the value from the previous access is needed as the address for the next access.**

I want to use LLVM to classify the data blocks of an application, **distinguishing between regular and irregular data blocks**, so that different hardware modules can be used to handle them separately to improve performance. The reason for using LLVM is that Spatial Accelerators typically use LLVM as the compiler frontend to convert source code to IR for backend mapping, which means this approach is widely applicable.

To classify the memory access behaviors of data blocks, my current idea is to **first convert the source code to IR and record all Load/Store IR**. Then, I plan to **traverse backward for each load/store IR to find if the value obtained by a previous load is used as the address for the current load/store**, as shown in the figure below. However, I find that if a brute-force search is used, it requires *O(N^2)* complexity, which might be criticized. I would like to ask if there is a smarter approach, or if my initial idea is fundamentally flawed? Thanks in advance for any help!

[![An Example to Find Memory Access Dependency in x86 Architecture](https://i.sstatic.net/rUgcim4k.png)](https://i.sstatic.net/rUgcim4k.png)

**Tags:** ds.algorithms, pl.programming-languages, program-analysis, memory
> **Comments:**
> **username_1**: iiuc, you want to construct the graph of explicit dependency between lines in a given assembly code. I think it should be possible to do so in linear time. Just keep the last line in which each of those dependency creating objects was updated.  
> **username_1**: if you want to go beyond explicit synthetic depends, e.g. through memory locations or stack, I think they problem then becomes as hard as executing the program itself (because of jumps and loops and recursion and...).  
> **username_0**: @Kaveh Thank you for your help. I am sorry that I might not fully understand your point. Are you suggesting that during a traversal of all the assembly code, we only need to record the last node of each dependency chain for comparison? E.g., if we have two dependency chains, A-B-C and D-E, when we reach node F, we only need to compare node F with nodes C or E to check for dependencies? However, is it possible that a middle node of a dependency chain might have a dependency with the current instruction being traversed?  

---

## 1 answers

### Answer by username_2 on 2024-10-17. Score: 0

You can modify the tuple of control flow graph and data flow graph, or its hybrid control/data flow graph (CDFG), to generate a dependency graph.

You may even be able to generate this, while producing the CDFG for LLVM.

Memory access pattern classification into regular blocks and irregular blocks can also be done with dynamic/binary analysis at run time, instead of static program analysis.

Memory access pattern classification is also ISA/hardware dependent, so you would have to process the output of code generation (usually in binary, or assembly code).


---

