DEV Community: Juro Zaw

Queues - DSA Notes 📝

Juro Zaw — Mon, 12 May 2025 22:21:36 +0000

🎯 Learning Goals

What are Queues and how to implement them?
What are their time complexities?

🧠 Key Concepts (aka My Notes)

FIFO - First In, First Out
- Enqueue = Pushing at the end
- Dequeue = Removing from the beginning
Achieve it using LinkedList

Think of this as a line (left and right) whereas a stack is vertical (top and bottom).

Enqueue

We are using singly linked list here.
Need to check for cases where queue is empty and where it is not

def enqueue(self, val):
    newNode = ListNode(val)
    if self.tail:
        self.tail.next = newNode
        self.tail = self.tail.next
    else:
        self.head = self.tail = newNode

⌚ Time complexity is O(1)

Dequeue

Let’s check if the queue is empty too and then return the value

def dequeue(self):
    # if the queue is empty
    if not self.head:
        return None

    val = self.head.val
    self.head = self.head.next
    if not self.head:
        self.tail = None
    return val

⌚ Time complexity is O(1)

There is also a ‘Deque’ data structure which allows you to enqueue and dequeue from both head and tail.

⌚ Time Complexities

Operation	Big-0
Enqueue	O(1)
Dequeue	O(1)

💪 LeetCode Problems

1700. Number of Students Unable to Eat Lunch (Link)
225. Implement Stack using Queues (Link)

Doubly Linked Lists - DSA Notes 📝

Juro Zaw — Fri, 09 May 2025 21:14:35 +0000

🎯 Learning Goals

What are doubly linked lists?
What are its operations’ time complexities?

🧠 Key Concepts (aka My Notes)

Two pointers (next and prev)
- Null prev means it is the head of the list

Insertion at End

Same as Singly Linked
But, make sure to update prev pointer too
The order is important
- Don’t update the tail pointer without updating the old tail’s next and NewListNode’s prev)

tail.next = NewListNode
NewListNode.prev = tail
# Update tail pointers
tail = tail.next

⌚ Time complexity is O(1)

Deletion at End

Deletion means just not having anything point to that last node
For this one, important to save the pointer to the node before the tail
- So that, we can set the tail pointer to that node.

Here, ListNode2 is just a variable name. It can be temp or anything.

ListNode2 = tail.prev
ListNode2.next = null
tail = ListNode2

⌚ Time complexity is O(1)

O(1) insertion and deletion means that theoretically we can use these guys are implement Stacks.

Access

Same as Singly Linked List, but can go both directions

⌚ Time complexity is O(n)

⌚ Time Complexities

Operation	Big-O
Access	O(n)
Search	O(n)
Insertion (end)	O(1)
Deletion (end)	O(1)

💪 LeetCode Problems

707. Design Linked List (Link)
1472. Design Browser History (Link)

Singly Linked Lists - DSA Notes 📝

Juro Zaw — Tue, 06 May 2025 00:00:28 +0000

🎯 Learning Goals

What are the characteristics of Singly Linked Lists?
What are its time complexities?

🧠 Key Concepts (aka My Notes)

What is a `ListNode`?

Has a value and a next pointer
- next is a reference to another ListNode
Order in memory may not be contiguous (unlike arrays which are)

Traversal

Simple while loop with a current pointer can be used:

cur = ListNode1
while cur:
    cur = cur.next

⌚ Time complexity is O(n) , where n is the number of nodes in the linked list

Now if the Linked List is circular (i.e. last node points back to first) traversing like this would cause an infinite loop.

It would be helpful if we’re keeping track of the head and the tail of the linked list using pointers

Insertion

Advantage over array is that inserting is always O(1) even if we insert in middle.

Let’s say we wanna add at the end or tail :

tail.next = NewListNode
tail = NewListNode
# or this line 'tail = tail.next', both are correct

⌚ Time complexity is O(1)

Deletion

Removing any node is constant time ASSUMING we have a pointer to the previous node.

Let’s say we wanna remove the second node:

head.next = head.next.next
# Just set the next pointer of head to the one after the deleted node

Can be assumed that garbage collection will take place for the deleted node

⌚ Time complexity is O(1)

For both of these operations, the caveat is if we don’t have a reference to the node at the desired position (head or tail), the time will still be O(n)

⌚ Time Complexities

Operation	Big-O
Reading/ Access	O(n)
Traversal/ Search	O(n)
Insertion	O(1)*
Deletion	O(1)*

*Assumes you have a reference to the node at the position (if not it is O(n) )

💪 LeetCode Problems

206. Reverse Linked List (Link)
21. Merge Two Sorted Lists (Link)

Stacks - DSA Notes 📝

Juro Zaw — Thu, 01 May 2025 16:46:36 +0000

🎯 Learning Goals

How are Stacks implemented?
What are the time complexities?

🧠 Key Concepts (aka My Notes)

Stacks

Dynamic arrays are already Stacks.
LIFO (Last In is the First Out)
There should be a pointer for the last element in the array.

Push

Appending an element to the end of a dynamic array

⌚ Time Complexity is O(1).

Push

Removing an element to the end of a dynamic array
It is wise to check if the stack is empty before popping

⌚ Time Complexity is O(1).

Peek

Returning an element to the end of a dynamic array

⌚ Time Complexity is O(1).

⌚ Time Complexity for Stacks

Operation	Big-O
Push	O(1)
Pop	O(1)
Peek	O(1)

💪 LeetCode Problems

155. Min Stack (Link)
20. Valid Parentheses (Link)

Dynamic Arrays - DSA Notes 📝

Juro Zaw — Thu, 01 May 2025 16:15:09 +0000

🎯 Learning Goal

What are the characteristics of dynamic arrays?
What are the time complexities of dynamic arrays?

🧠 Key Concepts (aka My Notes)

Dynamic Arrays

Can grow as elements are added.
Different languages have different default array size (Java = 10 and C# = 4)

Insertion at end (Pushing)

End Pointer (or length) is important!
Insert a value at arr[length] and resize if length >= capacity

# Insert n in the last position of the array
def pushback(self, n):
    if self.length == self.capacity:
        self.resize()

    # insert at next empty position
    self.arr[self.length] = n
    self.length += 1

⌚ Amortized Time Complexity is O(1)

This is amortized, meaning it's the average time taken for a sequence of pushing operations.

The resizing only happen when the array runs out of size, which does not happen on every push.

This is the same for deleting at end (popping)

Resizing

Copy the values to a new static array which is 2x the size
Deallocate the old array when everything has been copied over

def resize(self):
    # Create new array of double capacity
    self.capacity = 2 * self.capacity
    newArr = [0] * self.capacity 

    # Copy elements to newArr
    for i in range(self.length):
        newArr[i] = self.arr[i]
    self.arr = newArr

⌚ Time Complexity for resize is O(n)

🤔 Analyzing Time Complexity

Analyzing means we consider the sum of all operations

For example, to go from array of size 1 to size 8 requires 15 operations. Array operations went from 1 -> 2 -> 4 -> 8 (Don't forget to count the resizing as 1 extra operation.)

The last term is always greater than the sum of all the terms before it. (1+ 2 + 4 < 8).

The formula is that for any array size n, it will take at most 2n operations. (15 > 2 . 8)

Constants are dropped in time complexity analysis.

That's why resizing time complexity is O(n),

⌚ Time Complexity for Dynamic Arrays

Essentially the same as Static Arrays.

Operation	Big-O
Access	O(1)
Insertion (at end)	O(1)
Insertion (at middle)	O(n) because of shifting
Deletion (at end)	O(1)
Deletion (at middle)	O(n) because of shifting

💪 LeetCode Problems

1929. Concatenation of Array (Link)

Static Arrays - DSA Notes 📝

Juro Zaw — Wed, 30 Apr 2025 00:46:10 +0000

Introduction

Welcome to my new series on the BIG topic, Data Structures & Algorithms. Follow along with me as I learn everything about DSA to grind Leetcode!💪
Here, you will find all my notes on the topic. Starting everything off with Arrays. 😀

🎯 Learning Goal

What are the characteristics of static arrays?
What does reading, inserting and deleting look like for static arrays?

🧠 Key Concepts (aka My Notes)

Static Arrays

The size of a static array cannot change once declared. Once they are full, you cannot add more items.

Reading

Accessing a certain element in an array is always instant because you have the index number.

⌚ Time complexity is O(1).

O(1) means it's constant time. Even if the size of the data grows, the number of operations stay the same.

Traversing

You can use for/ while loops to go through an array and do a certain operation. (for example, printing everything in an array)

⌚ For an array of size n, the time complexity is O(n).

This means that the number of operations grow linearly with the size of the data.

Deleting

Deleting from End of Array

In statically typed languages (not JS or Python), you can remove element at the end (n-1 index) by the way of soft delete.

Soft Delete is basically overwriting the value of an element you wanna delete to 0, null or -1.

# The last element is overwritten by 0. Length is decremented.
def deleteEnd (arr, length):
    if length > 0:
        arr[length - 1] = 0
        length -= 1
    return length

⌚ Time complexity is O(1).

Deleting at `ith` index

Shift all values one position to the left of the index i
By shift to left, it means just overwrite the arr[i] with the value from the right

def deleteMiddle (arr, length, i):
    # From i + 1 to length - 1, shift left by one position
    for index in range(i + 1, length):
        arr[index - 1] = arr[index]

⌚ Time complexity is O(n).

This is because the worst case is we have to shift everything in the array of n size to
the left.

Insertion

Inserting at the End of Array

Insert at the length index.

def insertEnd (arr, length, capacity, value):
    if length < capacity:
        arr[length] = value

⌚ Time complexity is O(1).

Inserting at the `ith` index

Shift everything to the right of i
If it's full, the last element is lost
Then, insert at the specified index

def insertMiddle(arr, i, value, length):
    # Shift elements to the right to make space for the new element
    if i < length:
        # Index will decrement from the very end up to i
        # value at i will move and we overwrite the old value with our inserted value
        for index in range(length - 1, i - 1,-1):
            arr[index - 1] = arr[index]

        # Insert vale at specified index
        arr[i] = value

⌚ Time complexity is O(n).

⌚ Time Complexity

Operation	Big-O Time
Reading	O(1)
Insertion (at end)	O(1)
Insertion (at `i`)	O(n)
Deletion (at end)	O(1)
Deletion (at `i`)	O(n)

💪 LeetCode Problems

26. Remove Duplicates from Sorted Array (Link)
27. Remove Element (Link)

Tidy & Wrap Up - Project Stage 03

Juro Zaw — Thu, 17 Apr 2025 23:02:06 +0000

Introduction

Welcome to the final blog post of SPO600 series! 😄

This stage of the project will focus on enhancing some features as well as fix anything from stage 02.

You might remember from stage 02, the code was running on x86, but failing on AArch64 with a segmentation fault. This would be my first thing to fix before I could proceed with implementing the new functionality.

Debugging the AArch64 Segmentation Issue

Looking at the error backtrace from AArch64, I can see that my GCC pass is crashing in the compare_functions method when trying to print GIMPLE statements.

The issue is in how I'm calling print_gimple_stmt. On AArch64, the statement might have unexpected structures or null pointers that cause the printing function to crash. This part:

    if (gimple_code(stmt1) != gimple_code(stmt2)) {
      if (dump_file) {
        fprintf(dump_file, "Statement %zu: Different gimple codes\n", i);
        print_gimple_stmt(dump_file, stmt1, 0, TDF_SLIM);  // Line 164 - causing crash
        print_gimple_stmt(dump_file, stmt2, 0, TDF_SLIM);
      }
      return false;
    }

Add a safety check and I'll modify the function to print in another way as it is the one that is causing the issue.

  // Iterate through statements and compare them
  for (size_t i = 0; i < func1_stmts.size(); i++) {
    gimple *stmt1 = func1_stmts[i];
    gimple *stmt2 = func2_stmts[i];

    // Add safety check for null statements
    if (!stmt1 || !stmt2) {
      if (dump_file) {
        fprintf(dump_file, "Statement %zu: One or both statements are null\n", i);
      }
      return false;
    }

    // Check if statement codes are different
    if (gimple_code(stmt1) != gimple_code(stmt2)) {
      if (dump_file) {
        fprintf(dump_file, "Statement %zu: Different gimple codes (%d vs %d)\n", 
                i, gimple_code(stmt1), gimple_code(stmt2));

        // Use safer printing method without TDF_SLIM flag, which might be causing issues on AArch64
        fprintf(dump_file, "Statement 1 code: %d\n", gimple_code(stmt1));
        fprintf(dump_file, "Statement 2 code: %d\n", gimple_code(stmt2));
      }
      return false;
    }

    // Rest of the comparison logic...
  }
  // ...
}

Now, let's run this code in our /spo600/examples/test-clone directory. The details for running this code has been presented in the previous stage 02.

This is the output after running make all.

There seems to be no more segmentation fault and the program seemed to have been compiled by GCC. Let's check our dump file.

This seems to be working, so that's done!

Guaranteeing Prune Output for Every Function

During stage 2, I discovered that non‑clone functions (like main, .resolver, or any routine without a .<variant> suffix) were being silently skipped. There was no decision at all for these functions.

I want to fix it so that there is a prune decision for every single function, regardless of here is a variant or not.

First, as soon as we enter execute, if we deem it as not a clone by our is_clone_function, print a decision and return immediately.

  bool is_clone_or_default = is_clone_function(fndecl, base_name, variant);

  if (!is_clone_or_default) {
    const char *func_name = IDENTIFIER_POINTER(DECL_NAME(fndecl));
    if (dump_file)
      fprintf(dump_file, "NOPRUNE: %s\n", func_name);
    return 0;
  }

  if (is_clone_or_default) {
// The rest ...
}

Next, when we push a .default into the group, check if its the only member. If so, there’s nothing to prune against, so print "NOPRUNE: base.default" right away.

Change that part to this:

  if (is_clone_or_default) {
   // Some code.....

    auto &group = clone_groups[base_name];
    group.push_back(info);

    if (info.variant == ".default" && group.size() == 1) {
      if (dump_file)
        fprintf(dump_file, "NOPRUNE: %s%s\n", 
                base_name.c_str(), info.variant.c_str());
      return 0;
    }

Now, when we check the test code, we can see every function has a decision attached to it!

Default

Variant

Function without variant

Resolver

Main

So that is working!

When we run the same thing in AArch64 we can see that it runs as well.

Creating Test Cases

Now, we will need to create test cases to see if it can process multiple sets of cloned functions.

Source code for test cases: Here

The test will have 2 functions.

#include <stdio.h>
#include <stdlib.h>

#ifndef CLONE_ATTRIBUTE
#define CLONE_ATTRIBUTE
#endif

// Simple arithmetic function – expected to be PRUNED
CLONE_ATTRIBUTE
int add_numbers(int a, int b) {
    int result = a + b;
    if (result > 100) {
        return result - 50;
    } else {
        return result * 2;
    }
}

// Array-processing function – expected to be NOPRUNED
CLONE_ATTRIBUTE
void process_array(int *arr, int size) {
    for (int i = 0; i < size; i++) {
        if (arr[i] % 2 == 0) {
            arr[i] = arr[i] * 4 + 3;
        } else {
            arr[i] = arr[i] / 2;
        }
    }
}

int main(void) {
    // Test add_numbers
    printf("add_numbers(10,20) = %d\n", add_numbers(10, 20));
    printf("add_numbers(70,50) = %d\n", add_numbers(70, 50));

    // Test process_array
    int array[10] = {1,2,3,4,5,6,7,8,9,10};
    process_array(array, 10);

    printf("Processed array: ");
    for (int i = 0; i < 10; i++)
        printf("%d ", array[i]);
    printf("\n");

    return 0;
}

add_numbers is a very simple arithmetic function. The compiler can easily optimize both variants to nearly identical code. So it is a great candidate for PRUNE.
process_array has more data-dependent branching and loop-based behavior. The clones may diverge more due to architecture-specific vectorization, likely a NOPRUNE.
You need that CLONE_ATTRIBUTE for what we're going to do in the Makefile

Now, that's not all. We have created the test but we need to modify the Makefile. Essentially we want our Makefile to compile two versions per architecture. (PRUNE and NOTPRUNE).

We also want to inject the target_clones attribute via macro. (This was done in the sample test that we used before).

Add these to the Makefile:

# x86‑64 PRUNE build
clone-test-x86-tc1-prune: test1.c $(LIBRARIES)
    $(CC) -D 'CLONE_ATTRIBUTE=__attribute__((target_clones("default","popcnt")))' \
          -march=x86-64 $(CFLAGS) test1.c $(LIBRARIES) -o $@

# x86‑64 NOPRUNE build
clone-test-x86-tc1-noprune: test1.c $(LIBRARIES)
    $(CC) -D 'CLONE_ATTRIBUTE=__attribute__((target_clones("default","arch=x86-64-v3")))' \
          -march=x86-64 $(CFLAGS) test1.c $(LIBRARIES) -o $@

# AArch64 PRUNE build
clone-test-aarch64-tc1-prune: test1.c $(LIBRARIES)
    $(CC) -D 'CLONE_ATTRIBUTE=__attribute__((target_clones("default","rng")))' \
          -march=armv8-a $(CFLAGS) test1.c $(LIBRARIES) -o $@

# AArch64 NOPRUNE build
clone-test-aarch64-tc1-noprune: test1.c $(LIBRARIES)
    $(CC) -D 'CLONE_ATTRIBUTE=__attribute__((target_clones("default","sve2")))' \
          -march=armv8-a $(CFLAGS) test1.c $(LIBRARIES) -o $@

This is referenced from the professor's test case. Basically for each of our function in the test case there will be PRUNE and NOPRUNE builds. The CLONE_ATTRIBUTE helps us with that.

Make sure to add our builds in the BINARIES macro.

AARCH64_BINARIES = clone-test-aarch64-prune clone-test-aarch64-noprune clone-test-aarch64-tc1-prune clone-test-aarch64-tc1-noprune
X86_BINARIES = clone-test-x86-prune clone-test-x86-noprune clone-test-x86-tc1-prune clone-test-x86-tc1-noprune

Now run make all again, and check the dump files.

make all
nano clone-test-x86-tc1-noprune-test1.c.265t.kzaw
nano clone-test-x86-tc1-prune-test1.c.265t.kzaw

Test Case Results

x86 NOPRUNE Build

Default add_numbers:

Default process_array:

process_array.popcnt:

add_numbers.popcnt:

The function dumped 'NOPRUNE' for resolvers and main.

x86 PRUNE Build

Default add_numbers:

Default process_array:

process_array.popcnt:

add_numbers.popcnt:

The function dumped 'NOPRUNE' for resolvers and main.

You will notice that add_numbers is PRUNE for both builds. That's because it is too simple. Any modern architecture (even with vectorization, popcnt, etc.) will generate the same instructions for this function.

AArch64 NOPRUNE Build

Default add_numbers:

Default process_array:

process_array.sve2:

add_numbers.sve2:

The function dumped 'NOPRUNE' for resolvers and main.

AArch64 PRUNE Build

Default add_numbers:

Default process_array:

process_array.rng:

add_numbers.rng:

The function dumped 'NOPRUNE' for resolvers and main.

Source Code

Please note that all source code is available on my GitHub.

You will find 3 files under /stage03/

Makefile: Makefile needed for running tests
test1.c: Test file
tree-kzaw-fix-prune.cc: Updated pass

Conclusion

Overall, this specific project stage allowed me to understand more about writing test cases for the pass. We've learnt much about compiling and adding logic to pass in the previous stages, and learning about test cases is a full circle moment. I learnt not only about writing a specific test.c logic but also how to write a Makefile to run alongside the tests.

This whole project and SPO600 series enabled me to think deeper and dive into the world of assembly language. From the basic 6502 language to actually working on the gcc compiler, it's all such a cool experience. I will cherish the learnings I have obtained from this course, and I'm sure understanding the most basic language will help me become a better programmer! 😄

Thank you so much for following me along on this journey. Till next time ~

6502 Program Lab - Lab 3

Juro Zaw — Sat, 12 Apr 2025 00:00:07 +0000

Introduction

Welcome to Lab 3! 😄

In this lab, I will be creating a simple program in the 6502 assembly language. Before I tell you what program I am writing, there are some requirements:

Must work in 6502 Emulator
Must output to character screen and graphics screen
Must input from user keyboard
Must use arithmetic operations

Fulfilling these requirements, the program I am writing is a random number guessing game!

How the game plays: the player tries to guess a random number between 1 and 9. They get 5 tries, and the outcome is a bitmap display filled with a color (green for a win, red for a loss).

✅ The source code is provided at the end of this blog post after the whole thing has been walked through!

Let's start!

📌 Setup & ROM Routines

Before we get into the main game loop, I need to define a few ROM routines. These routines will handle things like screen clearing, keyboard input, and text output.

I also allocate zero page variables for fast access.

; ROM routines entry points
define SCINIT  $ff81    ; initialize/clear screen
define CHRIN   $ffcf    ; input character from keyboard
define CHROUT  $ffd2    ; output character to screen

; Zero Page Variables
define TEXT_PTR   $40  ; pointer for text (low byte)
define TEXT_PTR_H $41  ; pointer for text (high byte)
define GUESS      $42  ; user guess
define ATTEMPTS   $43  ; remaining attempts (5 tries)
define ANSWER     $45  ; correct answer (ASCII value)

* = $0600      ; Program starts here

    JSR SCINIT          ; Clear screen

📌 Random Number Generation

Let's start with this part as I want to make sure the random number is generating properly before continuing on.

We know that 6502 does not have true randomness. So we use pseudo-random behavior from system memory. I used the value at $FE (a common pseudo-random location), but filtered it to keep only ASCII '1' to '9'.

RANDOM:
getRandom:
    LDA $FE         ; Load a value from memory address $FE
    CMP #$31        ; Compare with ASCII '1' (value = $31)
    BCC getRandom   ; If it's less than '1', try again
    CMP #$3A        ; Compare with ASCII ':' (value = $3A, one past '9')
    BCS getRandom   ; If it's '9' or more, try again
    RTS             ; Return with a valid value in A

It's quite simple. We compare the $FE value so that it can be only between 1 and 9.

This loop continues until value is between $31 and $39, which are the ASCII values for '1' to '9'.

Then I use it in the main code (under that JSR SCINIT line):

    JSR RANDOM
    STA ANSWER

📌 Welcome Message!

While we're at the main code, let's set the stage for the game. I want to print a nice welcome message and give the player 5 tries. I also reused a simple PRINT subroutine that walks over null-terminated strings.

I want to show something like:

SELECT A NUMBER ( 1 - 9 )
YOU HAVE 5 CHANCES!

This should be straightforward. Please feel free to read the comments to see what it does in details.

Referenced from SPO600: Place a Message on the Character Display

    LDA #$05         ; Load 5 into A (the number of tries)
    STA ATTEMPTS     ; Store it in ATTEMPTS variable

    LDA #<TITLE      ; Load the low byte of TITLE address into A
    STA TEXT_PTR     ; Store it in TEXT_PTR (pointer to the string)

    LDA #>TITLE      ; Load the high byte of TITLE address
    STA TEXT_PTR_H   ; Store it in TEXT_PTR_H (high part of pointer)

    LDY #$00         ; Set index Y = 0
    JSR PRINT        ; Call the PRINT subroutine to display the message

PRINT:
    LDA (TEXT_PTR), Y    ; Load byte at address (TEXT_PTR + Y)
    BEQ DONE             ; If byte = 0 (null terminator), end of string
    JSR CHROUT           ; Otherwise, print the character
    INY                  ; Move to next character
    BNE PRINT            ; Loop until we hit null (BNE is always true unless Y wraps)
DONE:
    RTS

TITLE:
    DCB "S","E","L","E","C","T",32,"A",32,"N","U","M","B","E","R",32
    DCB "(",32,"1",32,"-",32,"9",32,")",13
    DCB "Y","O","U",32,"H","A","V","E",32,"5",32,"C","H","A","N","C","E","S","!",0

At this point, if you run the code, you should get something like this:

📌 The Main Game Loop

Now let's finish defining the main loop: it prints the input prompt, takes input, validates it, then compares it to the answer.

Printing the input prompt is basically the same as printing the title:

START:
    LDA #<INPUT         
    STA TEXT_PTR        
    LDA #>INPUT         
    STA TEXT_PTR_H      
    LDY #$00            
    JSR PRINT

INPUT:
    DCB 13,13
    DCB "E","N","T","E","R",32,"A",32,"N","U","M","B","E","R",32
    DCB "(",32,"1",32,"-",32,"9",32,")",":",32,0

After that, wait for input and then validate it.

WAIT_INPUT:
    JSR CHRIN           ; Wait for player keypress (returns ASCII in A)

    CMP #$31            ; Compare with ASCII '1'
    BMI WAIT_INPUT      ; If below, invalid → wait again
    CMP #$3A            ; Compare with ASCII ':'
    BPL WAIT_INPUT      ; If 9 or above (':'), invalid → wait again

    STA GUESS           ; Save valid guess to GUESS variable
    JSR CHROUT          ; Echo the guess back to screen (user feedback)

    CMP ANSWER          ; Compare guess with the correct answer
    BEQ WIN             ; If equal → player wins!
    BCC HIGHER          ; If less → guess is lower → suggest to go higher
    BCS LOWER           ; If more → guess is higher → suggest to go lower

We validate the input to prevent invalid characters. If it's a match, we jump to WIN. Otherwise, we give feedback.

📌 Feedback: Higher or Lower

You might have noticed HIGHER and LOWER when validating user input. It's basically just printing to the screen whether the number needs to be higher or not.

The condition is already done in the main loop. So just define the text and the printing logic that we have used already before:

HIGHER_TEXT:
    DCB 13,"I","T","'", "S",32,"H","I","G","H","E","R",0

LOWER_TEXT:
    DCB 13,"I","T","'", "S",32,"L","O","W","E","R",0

HIGHER:
    LDA #<HIGHER_TEXT
    STA TEXT_PTR
    LDA #>HIGHER_TEXT
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT
    JMP UPDATE_ATTEMPTS

LOWER:
    LDA #<LOWER_TEXT
    STA TEXT_PTR
    LDA #>LOWER_TEXT
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT
    JMP UPDATE_ATTEMPTS

📌 Track Attempts

Now, what else is left? We need to track the user's tries. After every wrong guess, we decrement the number of attempts and decide whether to continue or end the game.

We just reuse START if they still have guesses left.

UPDATE_ATTEMPTS:
    DEC ATTEMPTS
    LDA ATTEMPTS
    BEQ LOSE ; Defining this below
    JMP START

📌 Lose State

Okay, almost done. Let's define what happens when a player loses. The game shows a message, reveals the correct answer, then fills the screen with red.

Printing is the same as always. I want to also show what the answer was:

LOSE:
    LDA #<LOSE_TEXT
    STA TEXT_PTR
    LDA #>LOSE_TEXT
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT

    LDA #<ANSWER_TEXT
    STA TEXT_PTR
    LDA #>ANSWER_TEXT
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT

    LDA ANSWER
    JSR CHROUT

LOSE_TEXT:
    DCB 13,"Y","O","U",32,"L","O","S","T",32,"T","H","E",32,"G","A","M","E",0

ANSWER_TEXT:
    DCB 13,"T","H","E",32,"N","U","M","B","E","R",32,"W","A","S",32,0

And then, call the subroutine to fill the screen with red, after which you can jump to game over.

    JSR FILL_RED
    JMP GAME_OVER

Let's define FILL_RED, which is the function that fills the bitmap display with red when the player loses.

FILL_RED:
    LDA #$00
    STA $10              ; Low byte of screen memory pointer
    LDA #$02
    STA $11              ; High byte → $0200 = screen start
    LDX #$06             ; Fill up to $0600
    LDY #$00
    LDA #$02             ; Red color code (system-dependent)
red_loop:
    STA ($10), y         ; Store red color at screen location
    INY                  ; Next byte
    BNE red_loop         ; If Y didn't wrap → loop again
    INC $11              ; Move to next screen row (high byte of address)
    LDY #$00             ; Reset Y
    CPX $11              ; Compare to target memory limit
    BNE red_loop         ; Keep going until we hit limit
    RTS

📌 Win State

Printing to text display:

WIN_TEXT:
    DCB 13,"Y","O","U",32,"W","I","N","!",32,"I","T","'", "S",32,0

WIN:
    LDA #<WIN_TEXT
    STA TEXT_PTR
    LDA #>WIN_TEXT
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT

    LDA ANSWER
    JSR CHROUT

    JSR FILL_GREEN

Green fill function:

FILL_GREEN:
    LDA #$00
    STA $10
    LDA #$02
    STA $11
    LDX #$06
    LDY #$00
    LDA #$0D
green_loop:
    STA ($10), y
    INY
    BNE green_loop
    INC $11
    LDY #$00
    CPX $11
    BNE green_loop
    RTS

📌 Game Reset

After a win or loss, wait for a key press, then restart the game from the beginning:

GAME_OVER:
    JSR CHRIN
    JMP $0600

✅ SOURCE CODE ✅

; Number Guessing Game for 6502
; Guess the correct number (1-9). The answer is randomly generated each game.
; On win, the display fills with green; on loss, it fills with red.
; You get 5 tries to guess the number.

; ROM routines entry points
define SCINIT  $ff81    ; initialize/clear screen
define CHRIN   $ffcf    ; input character from keyboard
define CHROUT  $ffd2    ; output character to screen

; Zero Page Variables
define TEXT_PTR   $40  ; pointer for text (low byte)
define TEXT_PTR_H $41  ; pointer for text (high byte)
define GUESS      $42  ; user guess
define ATTEMPTS   $43  ; remaining attempts (5 tries)
define ANSWER     $45  ; correct answer (ASCII value)

* = $0600      ; Program starts here

    JSR SCINIT          ; Clear screen

    ; Generate random answer (1-9) using hardware randomness.
    ; The RANDOM subroutine returns an ASCII digit ('1'-'9') directly.
    JSR RANDOM
    STA ANSWER          ; Store the ASCII value

    LDA #$05            ; Set 5 attempts
    STA ATTEMPTS

    ; Print the title
    LDA #<TITLE
    STA TEXT_PTR 
    LDA #>TITLE
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT

START:
    ; Print the input prompt
    LDA #<INPUT
    STA TEXT_PTR
    LDA #>INPUT
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT

WAIT_INPUT:
    JSR CHRIN         ; Wait for user input (result in A)

    CMP #$31          ; Must be between ASCII '1' and '9'
    BMI WAIT_INPUT
    CMP #$3A
    BPL WAIT_INPUT

    STA GUESS         ; Store the user's guess
    JSR CHROUT        ; Echo the input on screen

    ; Compare the guess to the random answer
    CMP ANSWER
    BEQ WIN           ; Correct guess
    BCC HIGHER        ; If guess < answer, show "Higher"
    BCS LOWER         ; If guess > answer, show "Lower"

HIGHER:
    LDA #<HIGHER_TEXT
    STA TEXT_PTR
    LDA #>HIGHER_TEXT
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT
    JMP UPDATE_ATTEMPTS 

LOWER:
    LDA #<LOWER_TEXT
    STA TEXT_PTR
    LDA #>LOWER_TEXT
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT
    JMP UPDATE_ATTEMPTS 

UPDATE_ATTEMPTS:
    DEC ATTEMPTS      ; Decrease attempt count by 1
    LDA ATTEMPTS
    BEQ LOSE          ; If no attempts left, game over
    JMP START

LOSE:
    ; Print lose message
    LDA #<LOSE_TEXT
    STA TEXT_PTR 
    LDA #>LOSE_TEXT
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT

    ; Show the correct answer
    LDA #<ANSWER_TEXT
    STA TEXT_PTR
    LDA #>ANSWER_TEXT
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT
    LDA ANSWER
    JSR CHROUT        ; Print the answer

    JSR FILL_RED      ; Fill display with red
    JMP GAME_OVER

WIN:
    ; Print win message
    LDA #<WIN_TEXT
    STA TEXT_PTR 
    LDA #>WIN_TEXT
    STA TEXT_PTR_H
    LDY #$00
    JSR PRINT

    ; Show the correct answer
    LDA ANSWER
    JSR CHROUT        ; Print the answer

    JSR FILL_GREEN    ; Fill display with green

GAME_OVER:
    JSR CHRIN        ; Wait for any key press
    JMP $0600        ; Restart the game (generates new random answer)

; ---------------------------------------------------
; Subroutine RANDOM
; Generates a pseudo-random number using hardware randomness.
; Reads from memory location $FE until a valid candidate is found.
; Returns a valid ASCII digit in the range '1' to '9' (i.e., $31 to $39) in A.
RANDOM:
getRandom:
    LDA $FE         ; Get a pseudo-random candidate from hardware RNG
    CMP #$31        ; Check if candidate is >= '1' (ASCII $31)
    BCC getRandom   ; If candidate is less than '1', try again
    CMP #$3A        ; Check if candidate is less than ':' (ASCII $3A)
    BCS getRandom   ; If candidate is not less than $3A, try again
    RTS             ; Return valid candidate in A

; ---------------------------------------------------
; Subroutine PRINT
; Prints a null-terminated string pointed to by TEXT_PTR.
PRINT:
    LDA (TEXT_PTR), Y
    BEQ DONE        ; Zero terminator reached; stop printing
    JSR CHROUT      ; Output character
    INY
    BNE PRINT
DONE:
    RTS

; ---------------------------------------------------
; Subroutine FILL_GREEN
; Fills the display with green (color code $0D).
FILL_GREEN:
    LDA #$00
    STA $10         ; Set pointer low byte to 0
    LDA #$02
    STA $11         ; Set pointer high byte to 2 (base address $0200)
    LDX #$06        ; X = 6 (max for high-byte pointer)
    LDY #$00        ; Reset column index (Y) to 0
    LDA #$0D        ; Green color code
green_loop:
    STA ($10), y    ; Write green to display at pointer + Y
    INY             ; Increment column index
    BNE green_loop  ; Loop until Y wraps (256 pixels)
    INC $11         ; Move to next page (increment high-byte pointer)
    LDY #$00        ; Reset Y for new page
    CPX $11         ; Compare X with current pointer high byte
    BNE green_loop  ; Continue filling until done
    RTS

; ---------------------------------------------------
; Subroutine FILL_RED
; Fills the display with red (color code $02).
FILL_RED:
    LDA #$00
    STA $10         ; Set pointer low byte to 0
    LDA #$02
    STA $11         ; Set pointer high byte to 2 (base address $0200)
    LDX #$06        ; X = 6
    LDY #$00        ; Reset Y to 0
    LDA #$02        ; Red color code
red_loop:
    STA ($10), y    ; Write red to display at pointer + Y
    INY             ; Increment column index
    BNE red_loop    ; Loop until Y wraps (256 pixels)
    INC $11         ; Move to next page (increment high-byte pointer)
    LDY #$00        ; Reset Y for new page
    CPX $11         ; Compare X with current pointer high byte
    BNE red_loop    ; Continue filling until finished
    RTS

; ---------------------------------------------------
; Text Strings
TITLE:
    DCB "G","U","E","S","S",32
    DCB "A",32
    DCB "N","U","M","B","E","R",32
    DCB "B","E","T","W","E","E","N",32
    DCB "1",32
    DCB "T","O",32
    DCB "9",13
    DCB "Y","O","U",32
    DCB "H","A","V","E",32
    DCB "5",32
    DCB "T","R","I","E","S","!",0

INPUT:
    DCB 13,13
    DCB "E","N","T","E","R",32
    DCB "A",32
    DCB "N","U","M","B","E","R",32
    DCB "(", "1","-","9",")",":",32,0

HIGHER_TEXT:
    DCB 13
    DCB "H","I","G","H","E","R",".",".",".",0

LOWER_TEXT:
    DCB 13
    DCB "L","O","W","E","R",".",".",".",0

WIN_TEXT:
    DCB 13
    DCB "Y","O","U",32
    DCB "W","I","N","!",32
    DCB "T","H","E",32
    DCB "A","N","S","W","E","R",32
    DCB "I","S",32,0

LOSE_TEXT:
    DCB 13
    DCB "Y","O","U",32
    DCB "L","O","S","T",".",32
    DCB "G","A","M","E",32
    DCB "O","V","E","R","!",0

ANSWER_TEXT:
    DCB 13
    DCB "T","H","E",32
    DCB "A","N","S","W","E","R",32
    DCB "W","A","S",32,0

Testing it

Let's run the whole game to make sure that it is running correctly.

On run:

Low number should prompt 'HIGHER...':

High number should prompt 'LOWER...' :

A clip of getting it correct:

A clip of getting it wrong:

As you can see the code is running as intended! 😄

Conclusion

Tackling this lab reminded me how brutal and rewarding the 6502 assembly can be. There's no high-level logic, so much so that even printing can take a while to figure out. You really learn to appreciate every instruction.

It was fun though to figure out the game loop. Making subroutine is extremely helpful in keeping everything neat. My challenge was in figuring out the logic for generating random numbers. It was so simple in retrospect but I had to change my mindset on another logic to achieve it.

I hope this breakdown helped you follow the logic and maybe even inspired you to make something of your own in assembly.

See you next time~ 👋

Testing & Fixes - Project Stage 02

Juro Zaw — Sun, 06 Apr 2025 17:47:16 +0000

Introduction

Welcome back (again) to Project Stage 02! 😄

In the previous part, we implemented logic for our tree-kzaw.cc pass which have been set up in gcc since Project Stage 01. In this continued part of stage 02, I will be testing out our logic and adding any fixes as needed.

As always, I will be using aarch64 and x86 servers to test my logic.

❇️ Please find the source code here: GitHub ❇️

📌 Recompiling & Rebuilding

Now that our pass logic has been implemented in the previous blog, we will need to rebuild our gcc to update it. Fortunately, if we did all that stuff with Makefile.in from Project Stage 01, we won't have to wait to do a full gcc rebuild.

Run these commands:

cd ~/gcc-build-001
time make -j 24 |& tee build-stage2-01.log
make install

If nothing goes wrong, we should be good for testing!

📌 Testing

In each of our servers, there is a file in the path: /public/spo600-test-clone.tgz. Two binaries will be built once we extract this and use make: one for PRUNE test and one for NOTPRUNE.

We will run this code to extract it and go into the directory as follows:

tar xvf /public/spo600-test-clone.tgz
cd ~/spo600/examples/test-clone

I see see a Makefile, README.txt and some other .c and .h files. The README.txt shows me that running make will output two binaries:

test-clone-ARCH-prune
test-clone-ARCH-noprune where ARCH is either 'aarch64' or 'x86' depending on the server.

👉 Setting Up Makefile

Let's check the Makefile as there are some changes we must do.

Now there is a lot of things happening in there, but what we need to focus on is the gcc. Within the file, you may see something like:

clone-test-x86-prune: clone-test-core.c $(LIBRARIES)
        gcc -D 'CLONE_ATTRIBUTE=......

Here, the gcc means the server's root gcc, not our local gcc so we will change that.

Add this at the top. Make sure to change the directory with your install directory (not build directory):

# Use the locally built GCC
CC = $(HOME)/gcc-test-001/bin/gcc

Now replace all gcc with $(CC).

clone-test-x86-prune: clone-test-core.c $(LIBRARIES)
        $(CC) -D 'CLONE_ATTRIBUTE=......

This ensures that the gcc being used is our local one! While we're at it, uncomment the DUMP_ALL = 1 since we would want to check dump files to know whether our code worked or not.

# Set DUMP_ALL to a non-empty value to enable all GCC dumps
 DUMP_ALL = 1

I think we are all done with Makefile.

👉 Checking Dump Files

Now what we should do next is to run a make command and check out our dump files.

make all

When you have run this, ls to see the files in the directory. You will see a BUNCH of dump files.

Like this:

clone-test-core.c
clone-test-x86-noprune
clone-test-x86-noprune-clone-test-core.c.000i.cgraph
clone-test-x86-noprune-clone-test-core.c.000i.ipa-clones
clone-test-x86-noprune-clone-test-core.c.006t.original
.
.
.
clone-test-x86-prune
clone-test-x86-prune-clone-test-core.c.000i.cgraph
clone-test-x86-prune-clone-test-core.c.000i.ipa-clones
clone-test-x86-prune-clone-test-core.c.000i.type-inheritance

On a closer look, you may notice that it is in 2 groups: one for prune and one for noprune.

Now, I don't really know which one to check, but I'm assuming the ones with our pass's names could be a great place to start.

clone-test-x86-noprune-clone-test-core.c.265t.kzaw
clone-test-x86-prune-clone-test-core.c.265t.kzaw

That sounds about right, I can see some of our printed messages. Checking the prune dump file:

;; Function scale_samples (scale_samples.default, funcdef_no=23, decl_uid=3954, cgraph_uid=24, symbol_order=23)

__attribute__((target ("default"), target_clones ("default", "popcnt")))
void scale_samples (int16_t * in, int16_t * out, int cnt, int volume)
{
.
.
.
}

;; Function scale_samples.popcnt (scale_samples.popcnt, funcdef_no=25, decl_uid=3985, cgraph_uid=30, symbol_order=28)

>>>> Found potential clone: scale_samples.popcnt (base: scale_samples, variant: .popcnt)
>>>> Collected 165 statements from function scale_samples.popcnt
__attribute__((target ("popcnt"), target_clones ("default", "popcnt")))
void scale_samples.popcnt (int16_t * in, int16_t * out, int cnt, int volume)
{
.
.
.
}

We know that the code is being compiled so that is good. However the logic might not be correct. What we can see from this:

❌ It's not analyzing scale_samples, I asumme it's because of the variant format (function.variant). That function should be fixed.
❌ It's checking scale_samples.popcnt, but it's stopped after collecting statements. Why?
✅ It's skipping scale_samples.resolver, which it should.
✅ It's skipping sum_sample, because there's no variant of it.

Let's debug and fix it

📌 Debugging: PRUNE Case

I want to make sure that the prune case work first. So let's fix those issues.

👉 Issue 1: Not Analyzing the Default Function

The pass isn't recognizing scale_samples (the default function) because it's only looking for functions with a period (.) in their name.

We need to modify the is_clone_function method to also recognize the base function.

Instead of returning false if the dot is not found. We do another check to see if it's a default function with target_clones attribute.
If it is, mark it as a .default variant.

...
  // Check if it's a default function with target_clones attribute
  if (lookup_attribute("target_clones", DECL_ATTRIBUTES(decl))) {
    base_name = func_name;
    variant = ".default";  // Use .default to mark it as the default variant

    if (dump_file) {
      fprintf(dump_file, "Found default function with clones: %s\n", full_name);
    }
    return true;
  }

  return false;

👉 Issue 2: Fix Clone Comparison in `execute()`

Now that the default functions can come out of that compare function and continue with their statements being collected, we have to fix our comparison logic.

In our existing code, it just compares the first two variants it finds, which might not include the default function. It also makes a single pruning decision for the base name, not distinguishing between variants.

Let's change the execute() logic. Specifically in the part where we select the functions to compare from the clone_groups.

Here we added code to find the default function in the group. Then, set it up to compare all variants against the default function (not just the first two).

// Find the default variant to use as reference
      size_t default_idx = 0;
      for (size_t i = 0; i < clone_groups[base_name].size(); i++) {
        if (clone_groups[base_name][i].variant == ".default") {
          default_idx = i;
          break;
        }
      }

      // Compare each non-default variant with the default
      const function_info &default_info = clone_groups[base_name][default_idx];
      bool all_same = true;

Below is the new comparison logic.

There is now a loop to compare each variant against the default
Added individual pruning for each variant (if it matches default or not)
Added overall decision for default function (if all variants are same or not)

for (size_t i = 0; i < clone_groups[base_name].size(); i++) {
        if (i == default_idx) continue; // Skip comparing default to itself

        const function_info &variant_info = clone_groups[base_name][i];

        if (dump_file) {
          fprintf(dump_file, "Comparing %s%s with %s%s\n", 
                  base_name.c_str(), default_info.variant.c_str(),
                  base_name.c_str(), variant_info.variant.c_str());
        }

        bool are_same = compare_functions(default_info.stmts, variant_info.stmts);

        // If any variant differs from default, mark the group as different
        if (!are_same) {
          all_same = false;
          // Print the pruning decision for this specific variant
          if (dump_file) {
            fprintf(dump_file, "NOPRUNE: %s%s\n", base_name.c_str(), variant_info.variant.c_str());
          }
        } else {
          // Print the pruning decision for this specific variant
          if (dump_file) {
            fprintf(dump_file, "PRUNE: %s%s\n", base_name.c_str(), variant_info.variant.c_str());
          }
        }
      }

      // Print the overall pruning decision for the default function
      print_prune_decision(base_name, all_same);

I believe this should be good. Let's test it again.

👉 Test Changes

After running the make all again after changes, let's check dump files.

;; Function scale_samples (scale_samples.default, funcdef_no=23, decl_uid=3954, cgraph_uid=24, symbol_order=23)

Found default function with clones: scale_samples
Collected 165 statements from function scale_samples
Collected 165 statements from function scale_samples.default
__attribute__((target ("default"), target_clones ("default", "popcnt")))
void scale_samples (int16_t * in, int16_t * out, int cnt, int volume)
{
.
.
.
}

;; Function scale_samples.popcnt (scale_samples.popcnt, funcdef_no=25, decl_uid=3985, cgraph_uid=30, symbol_order=28)

Found potential clone: scale_samples.popcnt (base: scale_samples, variant: .popcnt)
Collected 165 statements from function scale_samples.popcnt
Collected 165 statements from function scale_samples.popcnt
Analyzing clones of function: scale_samples
Comparing scale_samples.default with scale_samples.popcnt
Functions are substantially the same
PRUNE: scale_samples.popcnt
NOPRUNE: scale_samples
__attribute__((target ("popcnt"), target_clones ("default", "popcnt")))
void scale_samples.popcnt (int16_t * in, int16_t * out, int cnt, int volume)
{
.
.
.
}

As you can see, it is working. We can see:

✅ Checking default, skipping logic when it's the only one
✅ Checking .popcnt variant, determining the variant should be PRUNE.
✅ Decision given for the function itself, since it has a variant, it should be PRUNE.

Here is the screenshot:

Great! Now we know our logic is working. How about for the NOPRUNE case?

📌 Debugging: NOPRUNE Case

Let's check the dump file, clone-test-x86-noprune-clone-test-core.c.265t.kzaw:

;; Function scale_samples (scale_samples.default, funcdef_no=23, decl_uid=3954, cgraph_uid=24, symbol_order=23)

Found default function with clones: scale_samples
Collected 165 statements from function scale_samples
Collected 165 statements from function scale_samples.default
__attribute__((target ("default"), target_clones ("default", "arch=x86-64-v3")))
void scale_samples (int16_t * in, int16_t * out, int cnt, int volume)
{
.
.
.
}

;; Function scale_samples.arch_x86_64_v3 (scale_samples.arch_x86_64_v3, funcdef_no=25, decl_uid=3985, cgraph_uid=30, sy>
Found potential clone: scale_samples.arch_x86_64_v3 (base: scale_samples, variant: .arch_x86_64_v3)
Collected 193 statements from function scale_samples.arch_x86_64_v3
Collected 193 statements from function scale_samples.arch_x86_64_v3
Analyzing clones of function: scale_samples
Comparing scale_samples.default with scale_samples.arch_x86_64_v3
Functions have different statement counts: 165 vs 193
NOPRUNE: scale_samples.arch_x86_64_v3
NOPRUNE: scale_samples
__attribute__((target ("arch=x86-64-v3"), target_clones ("default", "arch=x86-64-v3")))
void scale_samples.arch_x86_64_v3 (int16_t * in, int16_t * out, int cnt, int volume)
{
.
.
.
}

It is also working. We can see:

✅ Checking default, skipping logic when it's the only one.
✅ Checking .arch_x86_64_v3 variant, determining the variant should be NOPRUNE.
✅ Decision given for the function itself, since there is no clone, it should be NOPRUNE.

Screenshot:

📌 How about `AArch64`?

OKAY! So we know that our pass is working fine in the x86 server since so far, everything we have done is within that server.

Let's check it in the aarch64 server now. Hopefully, we don't have to change anything.

After running the make in our spo600/examples/test-clone directory, I got this:

[kzaw@aarch64-002 test-clone]$ make all
/home/kzaw/gcc-test-001/bin/gcc -c  vol_createsample.c -o vol_createsample.o
/home/kzaw/gcc-test-001/bin/gcc -D 'CLONE_ATTRIBUTE=__attribute__((target_clones("default","rng") ))'\
        -march=armv8-a -g -O3 -fno-lto  -ftree-vectorize  -fdump-tree-all -fdump-ipa-all -fdump-rtl-all \
        clone-test-core.c vol_createsample.o -o clone-test-aarch64-prune
clone-test-core.c:28:6: warning: Function Multi Versioning support is experimental, and the behavior is likely to change [-Wexperimental-fmv-target]
   28 | void scale_samples(int16_t *in, int16_t *out, int cnt, int volume) {
      |      ^~~~~~~~~~~~~
during GIMPLE pass: kzaw
dump file: clone-test-aarch64-prune-clone-test-core.c.265t.kzaw
clone-test-core.c: In function ‘scale_samples.rng’:
clone-test-core.c:28:6: internal compiler error: Segmentation fault
0x22cf17b internal_error(char const*, ...)
        /home/kzaw/git/gcc/gcc/diagnostic-global-context.cc:517
0xfe97fb crash_signal
        /home/kzaw/git/gcc/gcc/toplev.cc:322
0x22ef0ff pp_string(pretty_printer*, char const*)
        /home/kzaw/git/gcc/gcc/pretty-print.cc:2656
0x22f013f format_phase_2
        /home/kzaw/git/gcc/gcc/pretty-print.cc:2035
0x22f013f pretty_printer::format(text_info&)
        /home/kzaw/git/gcc/gcc/pretty-print.cc:1711
0x22f1cb3 pp_format(pretty_printer*, text_info*)
        /home/kzaw/git/gcc/gcc/pretty-print.h:594
0x22f1cb3 pp_printf(pretty_printer*, char const*, ...)
        /home/kzaw/git/gcc/gcc/pretty-print.cc:2578
0xc2f0c3 print_gimple_stmt(_IO_FILE*, gimple*, int, dump_flag)
        /home/kzaw/git/gcc/gcc/gimple-pretty-print.cc:159
0x1055597 compare_functions
        /home/kzaw/git/gcc/gcc/tree-kzaw.cc:163
0x1055597 execute
        /home/kzaw/git/gcc/gcc/tree-kzaw.cc:372
Please submit a full bug report, with preprocessed source (by using -freport-bug).
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.
make: *** [Makefile:38: clone-test-aarch64-prune] Error 1

That's a whole lot of words but what we can get from this is:

The crash definitely happened during our GIMPLE pass: kzaw
It happened at Line 163 (inside compare_functions) and Line 372 (inside execute)

Conclusion

Overall, this project stage 02 was a different level of difficult compared to stage 01. Where stage 01 had more issues with compiling, for this stage 02, a lot of effort went into creating the logic for the pass.

As you can see from my blog journey, I went through a lot of debugging for the pass to work as intended. Then again, it was different for each server, so more care needed to be put into the pass logic.

All in all, this stage jogged my memory on C/C++ language and made me research on a lot of gcc macro functions that could help me in what I am trying to achieve. I received help by working together with other classmates. Overall, this project was a challenge all the way from implementation to testing!

Thank you. 😄

Clone-Pruning Analysis Pass - Project Stage 02

Juro Zaw — Sat, 05 Apr 2025 01:32:13 +0000

Introduction

Welcome to Project Stage 02! 😄

In our last stage, we went through the journey of making a basic GCC pass that goes through statements and functions to print out simple statistics. Building off of it, for this stage, we are creating a more advanced pass.

To avoid extra implications, I will just try to overwrite the pass I already made in stage 01. As always, I will be using aarch64 and x86 servers to test my logic.

❇️ Please find the source code here: GitHub ❇️

📌 Understanding the Requirements

According to my course instructions (Here), let's summarize what we have to do this time around:

Identify cloned functions (name pattern function.variant)
Compare cloned functions to check if they are substantially the same.
Output a string on whether to prune the functions

Let's incrementally implement the code.

📌 Cleaning Up Pass Structure

Basing of our code in Stage 01, we're gonna set up the structure so that we can start fresh. Nothing special here. 😄

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "tree-pretty-print.h"
#include "gimple-iterator.h"
#include "gimple-walk.h"
#include "internal-fn.h"
#include "gimple-pretty-print.h"

// Additional headers needed for clone analysis
#include "gimple-ssa.h"
#include "cgraph.h"
#include "attribs.h"
#include "pretty-print.h"
#include "tree-inline.h"
#include "intl.h"
#include <map>
#include <string>
#include <vector>

namespace {

const pass_data pass_data_kzaw =
{
  GIMPLE_PASS, /* type */
  "kzaw", /* name */
  OPTGROUP_NONE, /* optinfo_flags */
  TV_TREE_NRV, /* tv_id */
  PROP_cfg , /* properties_required */
  0, /* properties_provided */
  0, /* properties_destroyed */
  0, /* todo_flags_start */
  0, /* todo_flags_finish */
};

class pass_kzaw : public gimple_opt_pass
{
public:
  pass_kzaw (gcc::context *ctxt)
    : gimple_opt_pass (pass_data_kzaw, ctxt)
  {}

  bool gate (function *) final override {
    return 1;
  }

  unsigned int execute (function *) final override;

private:
  // Helper methods for clone analysis will go here
};

// Pass execution code will go here

} // anonymous namespace

// Factory function that creates an instance of the pass
gimple_opt_pass *
make_pass_kzaw (gcc::context *ctxt)
{
  return new pass_kzaw (ctxt);
}

📌 Pseudocode for `execute()`

It's important to know what we are trying to do in execute() before implementing any function. Here is what I can come up with:

Get the function declaration (a function fun will be passed as argument)
Check if the function's name follows the pattern of a clone (i.e., contains a dot separating a base name and a variant).
If a clone is detected, add its info (statements, name, etc.) to a map of clones (mapped by base name)
If the clone group contains two or more variants, it compares the first two variants' statements
Log a prune decision

Since we are trying to store the function's information, we will need a data structure and the map group that I mentioned. You might have noticed from the above code that there is a private: block in our class. Let's add it there.

private:
  // Data structure to store function information
  struct function_info {
    tree decl;                 // Function declaration
    function *fun;             // Function pointer
    std::string base_name;     // Base function name (without variant)
    std::string variant;       // Variant part of the name
    std::vector<gimple *> stmts; // Statements in the function
  };

  std::map<std::string, std::vector<function_info>> clone_groups;

This pseudocode looks reasonable for now so let us continue!

📌 `is_clone_function`: Check for a Clone

Before we implement the code, we should add a helper method. Let's add our function signature in the private block.

Every signature of subsequent functions I create in this project will be added in this block. I will not state it explicitly from now on.

👉 Function Signature and Purpose

bool is_clone_function(tree decl, std::string &base_name, std::string &variant);

It takes a function declaration (decl) and two string references (base_name and variant).

The tree data structure is used to represent various programming constructs, such as expressions, statements, declarations, and types, in a uniform way.

Purpose
To check if a given function declaration is a clone function. A clone function is identified by having a dot (.) in its name that separates the base name from a variant suffix. The function returns true if the pattern is found and the function is not a resolver; otherwise, it returns false.

👉 Function Logic

We will get the name of the function and then look for a pattern. If it matches, return true, otherwise, false. Please note that it is important especially in working with GCC compilation process to print out any useful information to the dump file.

Source Code

bool
pass_kzaw::is_clone_function(tree decl, std::string &base_name, std::string &variant)
{
  // Get the function name
  const char *full_name = IDENTIFIER_POINTER(DECL_NAME(decl));
  std::string func_name(full_name);

  // Look for the '.variant' pattern in the function name
  size_t dot_pos = func_name.find('.');
  if (dot_pos != std::string::npos) {
    base_name = func_name.substr(0, dot_pos);
    variant = func_name.substr(dot_pos);

    // Skip resolver functions
    if (variant == ".resolver") {
      return false;
    }

    if (dump_file) {
      fprintf(dump_file, "Found potential clone: %s (base: %s, variant: %s)\n", 
              full_name, base_name.c_str(), variant.c_str());
    }
    return true;
  }

  return false;
}

📌 `collect_function_statements`: Collect Function Statements

We will need a function to collect all the statements from a function.

👉 Function Signature and Purpose

void collect_function_statements(function *fun, std::vector<gimple *> &stmts);

It takes a reference to a vector of gimple * (statements). Its goal is to collect all GIMPLE statements from the function into the provided vector.

Purpose
To go through all basic blocks in the given function and collect each GIMPLE statement from those blocks into the stmts vector.

👉 Function Logic

We did something like this in project stage 01.

Source Code

void
pass_kzaw::collect_function_statements(function *fun, std::vector<gimple *> &stmts)
{
  basic_block bb;

  // Clear the vector in case it's being reused
  stmts.clear();

  // Collect all statements in the function
  FOR_EACH_BB_FN(bb, fun) {
    for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
      gimple *stmt = gsi_stmt(gsi);
      stmts.push_back(stmt);
    }
  }

  if (dump_file) {
    fprintf(dump_file, "Collected %zu statements from function %s\n", 
            stmts.size(), function_name(fun));
  }
}

📌 `compare_functions`: Compare Functions

👉 Function Signature and Purpose

bool pass_kzaw::compare_functions(const std::vector<gimple *> &func1_stmts, 
    const std::vector<gimple *> &func2_stmts);

This function takes two vectors of GIMPLE statements and compares them structurally.

Purpose
To determine if the two functions are equal or not, ignoring minor differences like variable renaming. This function detects the clones by comparing their statements after grouping them by a common base name.

👉 Function Logic

Statement Count Check

We first check if the number of statements in both functions is the same. If they are different, it could count as being different.

if (func1_stmts.size() != func2_stmts.size()) {
  if (dump_file) {
    fprintf(dump_file, "Functions have different statement counts: %zu vs %zu\n", 
            func1_stmts.size(), func2_stmts.size());
  }
  return false;
}

Iterating Through Statements

Next, we will loop over the statements from both functions at the same time. For each pair at the same index, the first check is to compare their GIMPLE codes. (which denote the type of statement).

for (size_t i = 0; i < func1_stmts.size(); i++) {
  gimple *stmt1 = func1_stmts[i];
  gimple *stmt2 = func2_stmts[i];

  // Check if statement codes are different
  if (gimple_code(stmt1) != gimple_code(stmt2)) {
    if (dump_file) {
      fprintf(dump_file, "Statement %zu: Different gimple codes\n", i);
      print_gimple_stmt(dump_file, stmt1, 0, TDF_SLIM);
      print_gimple_stmt(dump_file, stmt2, 0, TDF_SLIM);
    }
    return false;
  }

Detailed Comparison based on Statement Type

A switch statement is used to perform type-specific comparisons for each GIMPLE statement.

⚠️ Now there are a LOT of GIMPLE statements and this code would be way complex and out of scope if we were to implement each of them. So I decided to only implement for 4: GIMPLE_ASSIGN, GIMPLE_CALL, GIMPLE_COND and GIMPLE_RETURN since these are the basic code logics.

Please also note that help was retrieved from community members at my Stack Overflow and Discord. Macros were also referenced from GCC Documentation. At this point of the project, I'm not really confident in the logic but I really appreciate everyone who helped me. 🙏.

  // Compare based on statement type
  switch (gimple_code(stmt1)) {

➡️ GIMPLE_ASSIGN (Assignment Statements)

For assignment statements, the function compares:

The right-hand side operation code.
The number of operands.
The operand types and, for constants, their exact values.

case GIMPLE_ASSIGN:
  {
    // Check operation code
    if (gimple_assign_rhs_code(stmt1) != gimple_assign_rhs_code(stmt2)) {
      if (dump_file) {
        fprintf(dump_file, "Assignment operation mismatch at statement %zu\n", i);
      }
      return false;
    }

    // Check operand count
    unsigned op_count1 = gimple_num_ops(stmt1);
    unsigned op_count2 = gimple_num_ops(stmt2);
    if (op_count1 != op_count2) {
      if (dump_file) {
        fprintf(dump_file, "Different number of operands at statement %zu\n", i);
      }
      return false;
    }

    // For constants and literals, values must match exactly
    for (unsigned j = 1; j < op_count1; j++) {
      tree op1 = gimple_op(stmt1, j);
      tree op2 = gimple_op(stmt2, j);

      if (TREE_CODE(op1) != TREE_CODE(op2)) {
        if (dump_file) {
          fprintf(dump_file, "Different operand types at statement %zu\n", i);
        }
        return false;
      }

      // For constants, compare values
      if (CONSTANT_CLASS_P(op1) && CONSTANT_CLASS_P(op2)) {
        if (!vrp_operand_equal_p(op1, op2)) {
          if (dump_file) {
            fprintf(dump_file, "Different constant values at statement %zu\n", i);
          }
          return false;
        }
      }
    }
  }
  break;

➡️ GIMPLE_CALL (Function Calls)

For function calls, the function checks:

That the type of function call (tree code) is the same.
If the call is direct (address expression), it compares the function declarations.
The number of arguments in the call.

case GIMPLE_CALL:
  {
    // Check if calling the same function
    tree func1 = gimple_call_fn(as_a<gcall *>(stmt1));
    tree func2 = gimple_call_fn(as_a<gcall *>(stmt2));

    if (TREE_CODE(func1) != TREE_CODE(func2)) {
      if (dump_file) {
        fprintf(dump_file, "Different function call types at statement %zu\n", i);
      }
      return false;
    }

    // If it's a direct function call, compare the function declarations
    if (TREE_CODE(func1) == ADDR_EXPR) {
      tree fn_decl1 = TREE_OPERAND(func1, 0);
      tree fn_decl2 = TREE_OPERAND(func2, 0);

      if (DECL_NAME(fn_decl1) != DECL_NAME(fn_decl2)) {
        if (dump_file) {
          fprintf(dump_file, "Calling different functions at statement %zu\n", i);
        }
        return false;
      }
    }

    // Check argument count
    unsigned arg_count1 = gimple_call_num_args(as_a<gcall *>(stmt1));
    unsigned arg_count2 = gimple_call_num_args(as_a<gcall *>(stmt2));
    if (arg_count1 != arg_count2) {
      if (dump_file) {
        fprintf(dump_file, "Different number of arguments in call at statement %zu\n", i);
      }
      return false;
    }
  }
  break;

➡️ GIMPLE_COND (Conditional Statements)

For conditional statements, the function compares the conditional codes of both statements.

case GIMPLE_COND:
  {
    // Check condition code
    enum tree_code code1 = gimple_cond_code(as_a<gcond *>(stmt1));
    enum tree_code code2 = gimple_cond_code(as_a<gcond *>(stmt2));
    if (code1 != code2) {
      if (dump_file) {
        fprintf(dump_file, "Different conditional codes at statement %zu\n", i);
      }
      return false;
    }
  }
  break;

➡️ GIMPLE_COND (Conditional Statements)

For return statements, the function checks whether one statement returns a value while the other does not.

case GIMPLE_RETURN:
  {
    // Check if one returns a value and the other doesn't
    tree ret_val1 = gimple_return_retval(as_a<greturn *>(stmt1));
    tree ret_val2 = gimple_return_retval(as_a<greturn *>(stmt2));

    if ((ret_val1 == NULL_TREE) != (ret_val2 == NULL_TREE)) {
      if (dump_file) {
        fprintf(dump_file, "One function returns a value, the other doesn't at statement %zu\n", i);
      }
      return false;
    }
  }
  break;

For any statement types not explicitly handled, the function assumes that if the GIMPLE code is the same, the statements are considered equal.

Successful Comparison

If all pairs of statements pass the comparison checks, the function logs that the functions are substantially the same and returns true.

// If we've made it this far, the functions are considered substantially the same
if (dump_file) {
  fprintf(dump_file, "Functions are substantially the same\n");
}
return true;

Source Code

bool
pass_kzaw::compare_functions(const std::vector<gimple *> &func1_stmts, 
                             const std::vector<gimple *> &func2_stmts)
{
  // First check: different statement count means different functions
  if (func1_stmts.size() != func2_stmts.size()) {
    if (dump_file) {
      fprintf(dump_file, "Functions have different statement counts: %zu vs %zu\n", 
              func1_stmts.size(), func2_stmts.size());
    }
    return false;
  }

  // Iterate through statements and compare them
  for (size_t i = 0; i < func1_stmts.size(); i++) {
    gimple *stmt1 = func1_stmts[i];
    gimple *stmt2 = func2_stmts[i];

    // Check if statement codes are different
    if (gimple_code(stmt1) != gimple_code(stmt2)) {
      if (dump_file) {
        fprintf(dump_file, "Statement %zu: Different gimple codes\n", i);
        print_gimple_stmt(dump_file, stmt1, 0, TDF_SLIM);
        print_gimple_stmt(dump_file, stmt2, 0, TDF_SLIM);
      }
      return false;
    }

    // Compare based on statement type
    switch (gimple_code(stmt1)) {
    case GIMPLE_ASSIGN:
      {
        // Check operation code
        if (gimple_assign_rhs_code(stmt1) != gimple_assign_rhs_code(stmt2)) {
          if (dump_file) {
            fprintf(dump_file, "Assignment operation mismatch at statement %zu\n", i);
          }
          return false;
        }

        // Check operand count
        unsigned op_count1 = gimple_num_ops(stmt1);
        unsigned op_count2 = gimple_num_ops(stmt2);
        if (op_count1 != op_count2) {
          if (dump_file) {
            fprintf(dump_file, "Different number of operands at statement %zu\n", i);
          }
          return false;
        }

        // For constants and literals, values must match exactly
        for (unsigned j = 1; j < op_count1; j++) {
          tree op1 = gimple_op(stmt1, j);
          tree op2 = gimple_op(stmt2, j);

          if (TREE_CODE(op1) != TREE_CODE(op2)) {
            if (dump_file) {
              fprintf(dump_file, "Different operand types at statement %zu\n", i);
            }
            return false;
          }

          // For constants, compare values
          if (CONSTANT_CLASS_P(op1) && CONSTANT_CLASS_P(op2)) {
            if (!vrp_operand_equal_p(op1, op2)) {
              if (dump_file) {
                fprintf(dump_file, "Different constant values at statement %zu\n", i);
              }
              return false;
            }
          }
        }
      }
      break;

    case GIMPLE_CALL:
      {
        // Check if calling the same function
        tree func1 = gimple_call_fn(as_a<gcall *>(stmt1));
        tree func2 = gimple_call_fn(as_a<gcall *>(stmt2));

        if (TREE_CODE(func1) != TREE_CODE(func2)) {
          if (dump_file) {
            fprintf(dump_file, "Different function call types at statement %zu\n", i);
          }
          return false;
        }

        // If it's a direct function call, compare the function declarations
        if (TREE_CODE(func1) == ADDR_EXPR) {
          tree fn_decl1 = TREE_OPERAND(func1, 0);
          tree fn_decl2 = TREE_OPERAND(func2, 0);

          if (DECL_NAME(fn_decl1) != DECL_NAME(fn_decl2)) {
            if (dump_file) {
              fprintf(dump_file, "Calling different functions at statement %zu\n", i);
            }
            return false;
          }
        }

        // Check argument count
        unsigned arg_count1 = gimple_call_num_args(as_a<gcall *>(stmt1));
        unsigned arg_count2 = gimple_call_num_args(as_a<gcall *>(stmt2));
        if (arg_count1 != arg_count2) {
          if (dump_file) {
            fprintf(dump_file, "Different number of arguments in call at statement %zu\n", i);
          }
          return false;
        }
      }
      break;

    case GIMPLE_COND:
      {
        // Check condition code
        enum tree_code code1 = gimple_cond_code(as_a<gcond *>(stmt1));
        enum tree_code code2 = gimple_cond_code(as_a<gcond *>(stmt2));
        if (code1 != code2) {
          if (dump_file) {
            fprintf(dump_file, "Different conditional codes at statement %zu\n", i);
          }
          return false;
        }
      }
      break;

    case GIMPLE_RETURN:
      {
        // Check if one returns a value and the other doesn't
        tree ret_val1 = gimple_return_retval(as_a<greturn *>(stmt1));
        tree ret_val2 = gimple_return_retval(as_a<greturn *>(stmt2));

        if ((ret_val1 == NULL_TREE) != (ret_val2 == NULL_TREE)) {
          if (dump_file) {
            fprintf(dump_file, "One function returns a value, the other doesn't at statement %zu\n", i);
          }
          return false;
        }
      }
      break;

    default:
      // For other statement types, we consider them the same if the code matches
      break;
    }
  }

  // If we've made it this far, the functions are considered substantially the same
  if (dump_file) {
    fprintf(dump_file, "Functions are substantially the same\n");
  }
  return true;
}

📌 `print_prune_decision`: Print Decision

Finally, this is the function that prints whether a function should be pruned or not.

👉 Function Signature and Purpose

void print_prune_decision(const std::string &base_name, bool should_prune);

Purpose
Logs a decision based on whether a clone function group (identified by its base name) should be pruned or not.

👉 Function Logic

Source Code

void
pass_kzaw::print_prune_decision(const std::string &base_name, bool should_prune)
{
  if (dump_file) {
    if (should_prune) {
      fprintf(dump_file, "PRUNE: %s\n", base_name.c_str());
    } else {
      fprintf(dump_file, "NOPRUNE: %s\n", base_name.c_str());
    }
  }
}

📌 `execute()`

Now that all of our required functions have been implemented, it's time to tie everything together by implementing the main execute() function.

👉 Function Logic

Source Code

unsigned int
pass_kzaw::execute(function *fun)
{
  // Get the function declaration
  tree fndecl = current_function_decl;

  // Skip external functions or those with no body
  if (!fndecl || DECL_EXTERNAL(fndecl) || !DECL_STRUCT_FUNCTION(fndecl)) {
    return 0;
  }

  // Check if this is a clone function
  std::string base_name, variant;
  bool is_clone = is_clone_function(fndecl, base_name, variant);

  if (is_clone) {
    // Collect statements in this function
    function_info info;
    info.decl = fndecl;
    info.fun = fun;
    info.base_name = base_name;
    info.variant = variant;
    collect_function_statements(fun, info.stmts);

    // Add to the appropriate clone group
    clone_groups[base_name].push_back(info);

    // Check if we've seen enough clones of this function to make a decision
    if (clone_groups[base_name].size() >= 2) {
      if (dump_file) {
        fprintf(dump_file, "Analyzing clones of function: %s\n", base_name.c_str());
      }

      // Compare the first two variants
      const function_info &info1 = clone_groups[base_name][0];
      const function_info &info2 = clone_groups[base_name][1];

      bool are_same = compare_functions(info1.stmts, info2.stmts);

      // Print the pruning decision
      print_prune_decision(base_name, are_same);

      // Clear the clone group after making the decision
      // This ensures we only emit one decision per base function
      clone_groups.erase(base_name);
    }
  }

  return 0;
}

Final Thoughts

I would like to end this part of the project stage 02 here. We have implemented the logic for the pass. I won't go into details of compiling and building gcc again as they have been mentioned in Lab 4 and Project Stage 01.

The next step will be to test out this logic in our x86 and aarch64 servers. Let us go to the next part of this Project Stage 02.

Thank you for coding with me! 😄

Fixing Issues & Continued - Project Stage 01

Juro Zaw — Wed, 02 Apr 2025 17:33:48 +0000

📌 Find My Source Code Here: GitHub

Hello everyone, welcome back!

This is a continuation of my Project 01 blog post. There were some errors in Project Stage 01 so we will be fixing that.

You can find the first part here: Link.

📌 Install Error?

So my issue was that I could not make install after running the make command in the directory. This is the error:

This error is vague but it seems to generally mean that

Makefile was corrupted or was not completed
Configure didn't finish properly
Wrong directory

In this case, i think that the first point makes the most sense to be the issue.

📌 Build Error?

So when I check the build.log to investigate, I saw a BUNCH of code lines that says undefined reference to .... Example of a part of the log:

This definitely means that make was not completed successfully, had an error at one point and all the error cascaded.

If I check config.log, I can also find some 'missing' files.

📌 Basic Code

This is the changed code, I used for my basic tree-kzaw.cc

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "tree-pretty-print.h"
#include "gimple-iterator.h"
#include "gimple-walk.h"
#include "internal-fn.h"
#include "gimple-pretty-print.h"

// Added headers:
#include "gimple-ssa.h"
#include "cgraph.h"
#include "attribs.h"
#include "pretty-print.h"
#include "tree-inline.h"
#include "intl.h"

// Test pass

namespace {

const pass_data pass_data_kzaw =
{
  GIMPLE_PASS, /* type */
  "kzaw", /* name */
  OPTGROUP_NONE, /* optinfo_flags */
  TV_TREE_NRV, /* tv_id */
  PROP_cfg , /* properties_required */
  0, /* properties_provided */
  0, /* properties_destroyed */
  0, /* todo_flags_start */
  0, /* todo_flags_finish */
};

class pass_kzaw : public gimple_opt_pass
{
public:
  pass_kzaw (gcc::context *ctxt)
    : gimple_opt_pass (pass_data_kzaw, ctxt)
  {}

  /* opt_pass methods: */
  bool gate (function *) final override {
      return 1;
  }

  unsigned int execute (function *) final override;

};

unsigned int
pass_kzaw::execute (function *) {
    struct cgraph_node *node;
    int func_cnt = 0;

    FOR_EACH_FUNCTION (node)
      {
        if (dump_file)
        {
            fprintf(dump_file, "=== Function %d Name '%s' ===\n", ++func_cnt, node->name() );
        }
      }

    if (dump_file)
    {
        fprintf(dump_file, "\n\n#### End kzaw diagnostics, start regular dump of current gimple ####\n\n\n");
    }

    return 0;  // Moved return statement outside the if block to ensure it always returns
}

} // anonymous namespace

// Factory function that creates an instance of the pass
gimple_opt_pass *
make_pass_kzaw (gcc::context *ctxt)
{
  return new pass_kzaw (ctxt);
}

📌 What did I do?

After trying at the hour for many many hours, I decided to rebuild the whole gcc from scratch. Yes, this would take long but it was the only viable option as the logs were too big of a size and complicated to decipher.

I deleted the ~/git/gcc and rebuilt the entire thing again.

However, I realized there are very important details that you will need to consider for creating your own GCC pass.

✅ Get the Names Right

The main error you could face is getting and putting the names. This is very IMPORTANT! For example, taking the naming convention from my code:

tree-name.cc: This is the name of your pass definition file. You will put your logic in here. When you add a .o to OBJS in Makefile.in, you are using the filename so it will be tree-name.o.
pass_name: This will typically be the name of your pass itself! Not to be mistaken with the file name. This is what you are using in passes.def where you will define a NEXT_PASS(pass_name).
make_pass_name: This is the name of function within your file. It will be used in the tree-pass.h header file so use it when declaring the function within the header.

✅ Get Directories Right

Specifically, please be carefully with where you are calling the commands from. They have to be very specific. Here are important ones:

Configure command: The configure command (~/git/gcc/configure --prefix=$HOME/gcc-test-001) need to be called from your build directory. (~/gcc-build-001/)
GCC subdirectory: Creating a pass with regards to gcc source code must be in ~/git/gcc/gcc.
Makefile remove: When you change Makefile.in for the first time, and you need to remove the initial Makefile. Make sure that you are in the ~/gcc-build-001/gcc subdirectory!

If everything goes and attention is detailed, the install will be successful!

Now let's move on 😄

📌 Test it Out

We have confirmation that our gcc is installed. Now we will need to test it out.

`test.c` file

Make a new test.c file:

#include <stdio.h>

void function1() {
    printf("I'm function1!\n");
}

void function2() {
    printf("I'm function2!\n");
}

void function3() {
    printf("I'm function3!\n");
}

int main() {
    function1(); 
    function2(); 
    function3();
    return 0;
}

Makefile

To make and run our new test.c file, we will need to add a new Makefile.

BINARIES=test
CCFLAGS=-g -O0 -fno-builtin -fdump-tree-kzaw

all: ${BINARIES}

test: test.c
    $$HOME/gcc-test-001/bin/gcc ${CCFLAGS} -o test test.c

clean:
    rm ${BINARIES} *.o || true

Things to note:

Add -fdump-tree-kzaw to check our dump file. (The dump file name is from our pass file name)
Make sure to configure our local gcc, not the server gcc. We define the path from our test directory.

Run command:

make test

Now check your dumpfile, you will see something like this which means it is working:

📌 Updating the Code

Now that our basic code is working, it is time to edit it so that it can count both the basic blocks and GIMPLE statements!

The goal is to traverse basic blocks and statements within a function, while the old code traverses functions in the entire program.

The main portion of the code we will be editing is the execute() function.

First, we'll modify the function signature to actually use the function *fun parameter.

unsigned int
pass_kzaw::execute (function *fun)

Next, we need to declare variables for going through basic blocks and counting both blocks and statements.

basic_block block;
int block_count = 0, statement_count = 0;

Instead of traversing all functions in the program with FOR_EACH_FUNCTION, we now use FOR_EACH_BB_FN to iterate through all basic blocks in the current function.

// Traverse basic blocks in the current function
FOR_EACH_BB_FN (block, fun)
{
  block_count++;
  if (dump_file)
  {
    fprintf (dump_file, "===== Basic block count: %d =====\n", block_count);
  }
...

For each basic block, we add a nested loop using gimple_stmt_iterator to traverse all statements within that block,

// For each basic block, traverse statements
  for (gimple_stmt_iterator gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
  {
    gimple *g = gsi_stmt (gsi);
    statement_count++;
    if (dump_file)
    {
      fprintf (dump_file, "----- Statement count: %d -----\n", statement_count);
      print_gimple_stmt (dump_file, g, 0, TDF_VOPS|TDF_MEMSYMS);
    }
  }
}

Finally, we add summary statistics that report the total number of basic blocks and statements encountered.

// Print summary information
if (dump_file)
{
  fprintf (dump_file, "------------------------------------\n");
  fprintf (dump_file, "Total Basic Blocks: %d\n", block_count);
  fprintf (dump_file, "Total Gimple Statements: %d\n", statement_count);
  fprintf (dump_file, "------------------------------------\n\n");
}

return 0;

Completed execute() Code:

unsigned int
pass_kzaw::execute (function *fun)
{
  basic_block block;
  int block_count = 0, statement_count = 0;

  // Traverse basic blocks in the current function
  FOR_EACH_BB_FN (block, fun)
  {
    block_count++;
    if (dump_file)
    {
      fprintf (dump_file, "===== Basic block count: %d =====\n", block_count);
    }

    // For each basic block, traverse statements
    for (gimple_stmt_iterator gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
    {
      gimple *g = gsi_stmt (gsi);
      statement_count++;
      if (dump_file)
      {
        fprintf (dump_file, "----- Statement count: %d -----\n", statement_count);
        print_gimple_stmt (dump_file, g, 0, TDF_VOPS|TDF_MEMSYMS);
      }
    }
  }

  // Print summary information
  if (dump_file)
  {
    fprintf (dump_file, "------------------------------------\n");
    fprintf (dump_file, "Total Basic Blocks: %d\n", block_count);
    fprintf (dump_file, "Total Gimple Statements: %d\n", statement_count);
    fprintf (dump_file, "------------------------------------\n\n");
  }

  return 0;
}

Once you have finished editing the tree-name.cc file and the logic, please rebuild the gcc in your build directory using make.

Note that we don't have to do all of these Makefile.in stuff as it is only done the first time you add a pass.

When you go to your test file, make and run again, this will be the output!

Dump File Output:

;; Function function1 (function1, funcdef_no=0, decl_uid=2335, cgraph_uid=1, symbol_order=0)

===== Basic block count: 1 =====
----- Statement count: 1 -----
# .MEM_2 = VDEF <.MEM_1(D)>
printf ("I\'m function1!\n");
----- Statement count: 2 -----
# VUSE <.MEM_2>
return;
------------------------------------
Total Basic Blocks: 1
Total Gimple Statements: 2
------------------------------------

void function1 ()
{
  <bb 2> :
  printf ("I\'m function1!\n");
  return;

}



;; Function function2 (function2, funcdef_no=1, decl_uid=2337, cgraph_uid=2, symbol_order=1)

===== Basic block count: 1 =====
----- Statement count: 1 -----
# .MEM_2 = VDEF <.MEM_1(D)>
printf ("I\'m function2!\n");
----- Statement count: 2 -----
# VUSE <.MEM_2>
return;
------------------------------------
Total Basic Blocks: 1
Total Gimple Statements: 2
------------------------------------

void function2 ()
{
  <bb 2> :
  printf ("I\'m function2!\n");
  return;

}



;; Function function3 (function3, funcdef_no=2, decl_uid=2339, cgraph_uid=3, symbol_order=2)

===== Basic block count: 1 =====
----- Statement count: 1 -----
# .MEM_2 = VDEF <.MEM_1(D)>
printf ("I\'m function3!\n");
----- Statement count: 2 -----
# VUSE <.MEM_2>
return;
------------------------------------
Total Basic Blocks: 1
Total Gimple Statements: 2
------------------------------------

void function3 ()
{
  <bb 2> :
  printf ("I\'m function3!\n");
  return;

}



;; Function main (main, funcdef_no=3, decl_uid=2341, cgraph_uid=4, symbol_order=3)

===== Basic block count: 1 =====
----- Statement count: 1 -----
# .MEM_2 = VDEF <.MEM_1(D)>
function1 ();
----- Statement count: 2 -----
# .MEM_3 = VDEF <.MEM_2>
function2 ();
----- Statement count: 3 -----
# .MEM_4 = VDEF <.MEM_3>
function3 ();
----- Statement count: 4 -----
_5 = 0;
===== Basic block count: 2 =====
----- Statement count: 5 -----
<L0>:
----- Statement count: 6 -----
# VUSE <.MEM_4>
return _5;
------------------------------------
Total Basic Blocks: 2
Total Gimple Statements: 6
------------------------------------

int main ()
{
  int D.2344;
  int _5;

  <bb 2> :
  function1 ();
  function2 ();
  function3 ();
  _5 = 0;

  <bb 3> :
<L0>:
  return _5;

}

This code can be run both in x86 and aarch64 servers!
That brings us to the end of Project Stage 01! 😄

Conclusion

This stage took me a few tries to get running, but that made me understand all the more about creating gcc passes. Even a simple thing such as creating a pass can take so long if you are not being cautious about your file names, function names and directories.

All my learnings from my errors are condensed into a section at the start of this post. Please make sure to check it out so that you don't repeat my mistakes.

I will see you in Project Stage 02. Please stay safe!

64-Bit Assembly Language - Lab 5

Juro Zaw — Sat, 22 Mar 2025 20:37:41 +0000

Introduction

Hi everybody! In lab 5, we are moving forward from 6502 assembly language to modern processors such as x86 and aarch64. Although 6502 is offers a minimal instruction set, these modern processors have far more advanced capabilities and architecture. In this lab, we will be exploring the assembly languages in them.

All the experimentations will be made in x86 and aarch64 remote servers.

Setting Up

In our class servers, the code examples are obtained through the path: /public/spo600-assembler-lab-examples.tgz.

We will extract this .tgz file using the command tar.

tar xvf /public/spo600-assembler-lab-examples.tgz

The code will be presented in this structure:

 spo600
 └── examples
     └── hello                     # "hello world" example programs
         ├── assembler
         │   ├── aarch64           # aarch64 gas assembly language version
         │   │   ├── hello.s
         │   │   └── Makefile
         │   ├── Makefile
         │   └── x86_64            # x86_64 assembly language versions
         │       ├── hello-gas.s   # ... gas syntax
         │       ├── hello-nasm.s  # ... nasm syntax
         │       └── Makefile
         └── c                     # Portable C versions
             ├── hello2.c          # ... using write()
             ├── hello3.c          # ... using syscall()
             ├── hello.c           # ... using printf()
             └── Makefile

📌 `AArch64` Assembly Program

First, we will look at aarch64 server. Log in and go to the AArch64 assembly example directory:

cd ~/spo600/examples/hello/assembler/aarch64

There is a hello.s file. This is the source file of our code!

Next, you will see that there is a Makefile in this location. This means that we can run make and compile our program. Build the program using the make command.

Based on the dependencies defined in the Makefile, make determines which parts of the code have changed and need to be rebuilt, then executes the necessary commands to update only those parts.

make

After this, you will see a binary file named hello in the directory. Run this resulting binary file.

./hello

It will show you a "Hello, world!" on your terminal.

Okay, now let's take a look at the code using objdump command. I want to compare the disassembled output of the object file (hello.o) to the source file (hello.s).

objdump -d hello.o > hello_disassembled.txt

Disassembled Output (hello.o)

hello.o:     file format elf64-littleaarch64


Disassembly of section .text:

0000000000000000 <_start>:
   0:   d2800020        mov     x0, #0x1                        // #1
   4:   10000001        adr     x1, 0 <_start>
   8:   d28001c2        mov     x2, #0xe                        // #14
   c:   d2800808        mov     x8, #0x40                       // #64
  10:   d4000001        svc     #0x0
  14:   d2800000        mov     x0, #0x0                        // #0
  18:   d2800ba8        mov     x8, #0x5d                       // #93
  1c:   d4000001        svc     #0x0

Source File (hello.s)

.text
.globl _start
_start:

        mov     x0, 1           /* file descriptor: 1 is stdout */
        adr     x1, msg         /* message location (memory address) */
        mov     x2, len         /* message length (bytes) */

        mov     x8, 64          /* write is syscall #64 */
        svc     0               /* invoke syscall */

        mov     x0, 0           /* status -> 0 */
        mov     x8, 93          /* exit is syscall #93 */
        svc     0               /* invoke syscall */

.data
msg:    .ascii      "Hello, world!\n"
len=    . - msg

Looking at these two files, the disassembly file is an accurate instruction-by-instruction translation into machine code from our source file. The only difference is when we use the msg label in the adr instruction. However, this arose from the nature of how symbols are represented in disassembled code.

Modifying the `AArch64` Assembly Program

Here is a basic loop in AArch64 assembler.

 .text
 .globl _start
 min = 0                          /* starting value for the loop index; **note that this is a symbol (constant)**, not a variable */
 max = 6                         /* loop exits when the index hits this number (loop condition is i<max) */
 _start:
     mov     x19, min
 loop:

     /* ... body of the loop ... do something useful here ... */

     add     x19, x19, 1     /* increment the loop counter */
     cmp     x19, max        /* see if we've hit the max */
     b.ne    loop            /* if not, then continue the loop */

     mov     x0, 0           /* set exit status to 0 */
     mov     x8, 93          /* exit is syscall #93 */
     svc     0               /* invoke syscall */

The code is looping 6 times (max is 6). It stores the loop's index in register 19 (x19) to keep track of iterations. The body of the loop is empty right now.

☑️ Print Loop

Let's change this code so that it prints out "Loop" on every iteration. We added a .data section and added the print in the body of the loop.
Change hello.s like below:

.text
.globl _start

min = 0                          /* starting value for the loop index */
max = 6                          /* loop exits when the index hits this number */

_start:
    mov     x19, min            /* initialize loop counter */
loop:
    /* Print "Loop" message */
    mov     x0, 1               /* file descriptor: 1 is stdout */
    adr     x1, msg             /* message location (memory address) */
    mov     x2, len             /* message length (bytes) */
    mov     x8, 64              /* write is syscall #64 */
    svc     0                   /* invoke syscall */

    add     x19, x19, 1         /* increment the loop counter */
    cmp     x19, max            /* see if we've hit the max */
    b.ne    loop                /* if not, then continue the loop */

    mov     x0, 0               /* set exit status to 0 */
    mov     x8, 93              /* exit is syscall #93 */
    svc     0                   /* invoke syscall */

.data
msg:    .ascii      "Loop\n"
len=    . - msg

Test this new code by using make and running

make clean
make
./hello

Output:

[kzaw@aarch64-002 aarch64]$ ./hello
Loop
Loop
Loop
Loop
Loop
Loop

☑️ Print Loop and Index Number

Let's change the code again so that it will print Loop: # where '#' is the current index number.

To do that, we will need to convert our loop counter number to its ASCII character representation. In ASCII/ISO-8859-1/Unicode UTF-8, the digit characters are in the range 48-57 (0x30-0x39).

add     x20, x19, #48       /* x20 = x19 + 48 (ASCII '0') */

This converts the loop counter in register 19 (x19) by adding 48 value (ASCII code for '0') and stores the new value in x20. For example,

when x19 = 0, x20 becomes 48 (ASCII '0').
when x19 = 1, x20 becomes 49 (ASCII '1').
And so on...

Next, define our message.

msg:    .ascii      "Loop: #\n"    /* # is a placeholder for the digit */

I added this below code into the body of the loop. What's happening here is that I am getting the address of the msg, and then adding an offset of 6 bytes to point to the position after "Loop: ". (which is 6 characters long).

The strb instruction writes a byte from a register into a memory.

w20 is the 32 bit view of x20. When used with strb, this means we take the lowest 8 bits (1 byte) from that register. In this context, where x20 is pointing to an ASCII digit (which takes 1 byte), the instruction will ignore the other 24 bits and ensure unnecessary space isn't taken.

[x21] is the location to store the ASCII digit to. Now this whole thing means the instruction will write that ASCII digit to the memory location pointed to by x21 ('#').

adr     x21, msg            /* Get address of message */
add     x21, x21, #6        /* Position of the digit character (after "Loop: ") */
strb    w20, [x21]          /* Store the ASCII character at that position */

✨
Modified Code:

.text
.globl _start

min = 0                          /* starting value for the loop index */
max = 6                          /* loop exits when the index hits this number */

_start:
    mov     x19, min            /* initialize loop counter */
loop:
    /* Convert loop counter to ASCII character */
    add     x20, x19, #48       /* x20 = x19 + 48 (ASCII '0') */

    /* Store the ASCII digit in the message */
    adr     x21, msg            /* Get address of message */
    add     x21, x21, #6        /* Position of the digit character (after "Loop: ") */
    strb    w20, [x21]          /* Store the ASCII character at that position */

    /* Print message with loop counter */
    mov     x0, 1               /* file descriptor: 1 is stdout */
    adr     x1, msg             /* message location (memory address) */
    mov     x2, len             /* message length (bytes) */
    mov     x8, 64              /* write is syscall #64 */
    svc     0                   /* invoke syscall */

    add     x19, x19, 1         /* increment the loop counter */
    cmp     x19, max            /* see if we've hit the max */
    b.ne    loop                /* if not, then continue the loop */

    mov     x0, 0               /* set exit status to 0 */
    mov     x8, 93              /* exit is syscall #93 */
    svc     0                   /* invoke syscall */

.data
msg:    .ascii      "Loop: #\n"    /* # is a placeholder for the digit */
len=    . - msg

Output:

[kzaw@aarch64-002 aarch64]$ ./hello
Loop: 0
Loop: 1
Loop: 2
Loop: 3
Loop: 4
Loop: 5

☑️ Loop From 00 - 32

The next requirement is to loop from 00 - 32, printing in 2-digit decimal numbers. Besides changing the max symbol to 33, there are other important changes we must do.

We copy the loop counter to x22.

mov     x22, x19            /* Copy loop counter to x22 */

Next, we need to change our code to cater for two-digit conversion.
Before, it was just adding the ASCII number to our counter and that was it. Now it is more complicated.

How we calculate the tens digit is basically divide by 10. The udiv instruction gets the quotient in the division.

So x20 = x22 / 10

/* Calculate tens digit: quotient of division by 10 */
mov     x23, #10            /* Set divisor to 10 */
udiv    x20, x22, x23       /* x20 = x22 / 10 (quotient = tens digit) */

Now that the tens digit is extracted, we can get the ones digit by getting the remainder. To do this, we will use mul to multiply the quotient with 10. This value is then subtracted from original value to get the remainder.

/* Calculate ones digit: remainder of division by 10 */
mul     x24, x20, x23       /* x24 = quotient * 10 */
sub     x21, x22, x24       /* x21 = original - (quotient * 10) = remainder */

After all of this, we can convert everything to ASCII.

/* Convert digits to ASCII */
add     x20, x20, #48       /* Convert tens digit to ASCII */
add     x21, x21, #48       /* Convert ones digit to ASCII */

Let me show you a table of registers, comparing the old and new so we can understand better.

Register	Original Purpose	New Purpose
x19	Loop counter	Loop counter (unchanged)
x20	ASCII digit	Tens digit (after conversion to ASCII)
x21	Message pointer	Ones digit (after conversion to ASCII)
x22	–	Copy of loop counter for calculations
x23	–	Constant value 10 (divisor)
x24	–	Pointer for message buffer manipulation

Calculation is completed! Change the logic where we change the message to accommodate the two digits.

/* Store the ASCII digits in the message */
adr     x24, msg            /* Get address of message */
add     x24, x24, #6        /* Position of the first digit (after "Loop: ") */
strb    w20, [x24]          /* Store the tens digit */
add     x24, x24, #1        /* Move to the position of the second digit */
strb    w21, [x24]          /* Store the ones digit */

✨
Modified Code:

.text
.globl _start

min = 0                          /* starting value for the loop index */
max = 33                         /* loop exits when the index hits this number */

_start:
    mov     x19, min            /* initialize loop counter */
loop:
    /* Convert loop counter to two ASCII digits */
    mov     x22, x19            /* Copy loop counter to x22 */

    /* Calculate tens digit: quotient of division by 10 */
    mov     x23, #10            /* Set divisor to 10 */
    udiv    x20, x22, x23       /* x20 = x22 / 10 (quotient = tens digit) */

    /* Calculate ones digit: remainder of division by 10 */
    mul     x24, x20, x23       /* x24 = quotient * 10 */
    sub     x21, x22, x24       /* x21 = original - (quotient * 10) = remainder */

    /* Convert digits to ASCII */
    add     x20, x20, #48       /* Convert tens digit to ASCII */
    add     x21, x21, #48       /* Convert ones digit to ASCII */

    /* Store the ASCII digits in the message */
    adr     x24, msg            /* Get address of message */
    add     x24, x24, #6        /* Position of the first digit (after "Loop: ") */
    strb    w20, [x24]          /* Store the tens digit */
    add     x24, x24, #1        /* Move to the position of the second digit */
    strb    w21, [x24]          /* Store the ones digit */

    /* Print message with loop counter */
    mov     x0, 1               /* file descriptor: 1 is stdout */
    adr     x1, msg             /* message location (memory address) */
    mov     x2, len             /* message length (bytes) */
    mov     x8, 64              /* write is syscall #64 */
    svc     0                   /* invoke syscall */

    add     x19, x19, 1         /* increment the loop counter */
    cmp     x19, max            /* see if we've hit the max */
    b.ne    loop                /* if not, then continue the loop */

    mov     x0, 0               /* set exit status to 0 */
    mov     x8, 93              /* exit is syscall #93 */
    svc     0                   /* invoke syscall */

.data
msg:    .ascii      "Loop: ##\n"   /* ## are placeholders for the two digits */
len=    . - msg

Output:

[kzaw@aarch64-002 aarch64]$ ./hello
Loop: 00
Loop: 01
...
Loop: 09
Loop: 10
...
Loop: 32

☑️ Loop Without Trailing Zeros

The next change we're making is removing the leading zero for single-digit numbers.

To make this happen, we need to implement conditional logic that detects whether we're dealing with a single-digit or double-digit number, and formats the output accordingly.

We need to use different message formats depending on the number's value:

For numbers 0-9: Use "Loop: #" (notice two spaces after the colon)
For numbers 10-32: Use "Loop: ##" (notice one space after the colon)

.data
msg1:   .ascii      "Loop:  #\n"   /* Single-digit format (note: two spaces after colon) */
len1=   . - msg1
msg2:   .ascii      "Loop: ##\n"   /* Double-digit format (note: one space after colon) */
len2=   . - msg2

The KEY change is this conditional check. We compare the tens digit with the ASCII value '0'. If it's not '0', then we know we have a two-digit number. We will make a new double_digit function for our condition.

/* Determine if number is single or double digit */
cmp     x20, #48            /* Compare tens digit to ASCII '0' */
b.ne    double_digit        /* If not '0', it's a double-digit number */

If it's not double digit, then we continue on to the single digit case. Use msg1 and store in position 6. After the logic, jump to the common print_msg routine.

/* Single-digit case (0-9) */
adr     x24, msg1           /* Get address of single-digit message */
strb    w21, [x24, #6]      /* Store ones digit at position after "Loop: " */
mov     x1, x24             /* Set message address for print */
mov     x2, len1            /* Set message length */
b       print_msg           /* Jump to print routine */

If it's double digit, we would jump to double_digit routine. Use msg2, set the length and address up for printing and then fall through to the print logic.

double_digit:
    /* Double-digit case (10-32) */
    adr     x24, msg2           /* Get address of double-digit message */
    strb    w20, [x24, #6]      /* Store tens digit */
    strb    w21, [x24, #7]      /* Store ones digit */
    mov     x1, x24             /* Set message address for print */
    mov     x2, len2            /* Set message length */

This is the printing logic below.

print_msg:
    /* Print message with loop counter */
    mov     x0, 1               /* file descriptor: 1 is stdout */
    mov     x8, 64              /* write is syscall #64 */
    svc     0                   /* invoke syscall */

✨
Modified Code:

.text
.globl _start

min = 0                          /* starting value for the loop index */
max = 33                         /* loop exits when the index hits this number */

_start:
    mov     x19, min            /* initialize loop counter */
loop:
    /* Convert loop counter to two ASCII digits */
    mov     x22, x19            /* Copy loop counter to x22 */

    /* Calculate tens digit: quotient of division by 10 */
    mov     x23, #10            /* Set divisor to 10 */
    udiv    x20, x22, x23       /* x20 = x22 / 10 (quotient = tens digit) */

    /* Calculate ones digit: remainder of division by 10 */
    mul     x24, x20, x23       /* x24 = quotient * 10 */
    sub     x21, x22, x24       /* x21 = original - (quotient * 10) = remainder */

    /* Convert digits to ASCII */
    add     x20, x20, #48       /* Convert tens digit to ASCII */
    add     x21, x21, #48       /* Convert ones digit to ASCII */

    /* Determine if number is single or double digit */
    cmp     x20, #48            /* Compare tens digit to ASCII '0' */
    b.ne    double_digit        /* If not '0', it's a double-digit number */

    /* Single-digit case (0-9) */
    adr     x24, msg1           /* Get address of single-digit message */
    strb    w21, [x24, #7]      /* Store ones digit at position after "Loop:  " */
    mov     x1, x24             /* Set message address for print */
    mov     x2, len1            /* Set message length */
    b       print_msg           /* Jump to print routine */

double_digit:
    /* Double-digit case (10-32) */
    adr     x24, msg2           /* Get address of double-digit message */
    strb    w20, [x24, #6]      /* Store tens digit */
    strb    w21, [x24, #7]      /* Store ones digit */
    mov     x1, x24             /* Set message address for print */
    mov     x2, len2            /* Set message length */

print_msg:
    /* Print message with loop counter */
    mov     x0, 1               /* file descriptor: 1 is stdout */
    mov     x8, 64              /* write is syscall #64 */
    svc     0                   /* invoke syscall */

    add     x19, x19, 1         /* increment the loop counter */
    cmp     x19, max            /* see if we've hit the max */
    b.ne    loop                /* if not, then continue the loop */

    mov     x0, 0               /* set exit status to 0 */
    mov     x8, 93              /* exit is syscall #93 */
    svc     0                   /* invoke syscall */

.data
msg1:   .ascii      "Loop:  #\n"   /* Single-digit format (note: two spaces after colon) */
len1=   . - msg1
msg2:   .ascii      "Loop: ##\n"   /* Double-digit format (note: one space after colon) */
len2=   . - msg2

Output:

Loop:  0
Loop:  1
Loop:  2
...
Loop:  9
Loop: 10
Loop: 11
...
Loop: 32

☑️ Loop with Hex Output (0 - 20)

Now, let's say we want to output in hex instead of decimal. Remove the single vs. double digit branch. These are the changes you can make.

We will now divide by 16 instead of 10. This makes the quotient the “high nibble” (first hexadecimal digit) and the remainder the “low nibble.”

    mov     x23, #16

For each nibble, check whether its value is less than 10. If it is, convert it to ASCII by adding 48. If it's not, we add 55 so that 1o becomes 65 ('A'), 11 becomes 66 ('B'), etc.

Here's that logic for the high nibble. The same is applied to low nibble.

    cmp     x20, #10            /* Check if high nibble is less than 10 */
    blt     high_digit_decimal
    add     x20, x20, #55       /* For hex A-F */
    b       high_digit_done
high_digit_decimal:
    add     x20, x20, #48       /* For digits 0-9 */
high_digit_done:

✨
Modified Code:

.text
.globl _start

min = 0                          /* starting value for the loop index */
max = 33                         /* loop exits when the index hits this number */

_start:
    mov     x19, min            /* initialize loop counter */
loop:
    /* Convert loop counter to two hexadecimal digits */
    mov     x22, x19            /* Copy loop counter to x22 */

    /* Calculate high nibble: quotient of division by 16 */
    mov     x23, #16            /* Set divisor to 16 for hex */
    udiv    x20, x22, x23       /* x20 = x22 / 16 (high nibble) */

    /* Calculate low nibble: remainder of division by 16 */
    mul     x24, x20, x23       /* x24 = high nibble * 16 */
    sub     x21, x22, x24       /* x21 = original - (high nibble * 16) = low nibble */

    /* Convert high nibble to ASCII */
    cmp     x20, #10            /* Check if high nibble is less than 10 */
    blt     high_digit_decimal
    /* For hex A-F: add 55 (10+55=65 -> 'A') */
    add     x20, x20, #55       
    b       high_digit_done
high_digit_decimal:
    add     x20, x20, #48       /* For digits 0-9: add 48 ('0') */
high_digit_done:

    /* Convert low nibble to ASCII */
    cmp     x21, #10            /* Check if low nibble is less than 10 */
    blt     low_digit_decimal
    /* For hex A-F */
    add     x21, x21, #55       
    b       low_digit_done
low_digit_decimal:
    add     x21, x21, #48       /* For digits 0-9 */
low_digit_done:

    /* Store the ASCII characters in the message template */
    adr     x24, msg           /* Get address of the message template */
    strb    w20, [x24, #6]      /* Store high nibble at position after "Loop: " */
    strb    w21, [x24, #7]      /* Store low nibble */

    /* Print message */
    mov     x1, x24             /* Set message address for print */
    mov     x2, len             /* Set message length */
    mov     x0, 1               /* file descriptor: 1 is stdout */
    mov     x8, 64              /* write is syscall #64 */
    svc     0                   /* invoke syscall */

    add     x19, x19, 1         /* increment the loop counter */
    cmp     x19, max            /* see if we've hit the max */
    b.ne    loop                /* if not, then continue the loop */

    mov     x0, 0               /* set exit status to 0 */
    mov     x8, 93              /* exit is syscall #93 */
    svc     0                   /* invoke syscall */

.data
msg:   .ascii      "Loop: ##\n"   /* Message format for hexadecimal output */
len=   . - msg

Output:

[kzaw@aarch64-002 aarch64]$ ./hello
Loop: 00
Loop: 01
Loop: 02
Loop: 03
Loop: 04
Loop: 05
Loop: 06
Loop: 07
Loop: 08
Loop: 09
Loop: 0A
Loop: 0B
Loop: 0C
Loop: 0D
Loop: 0E
Loop: 0F
Loop: 10
Loop: 11
Loop: 12
Loop: 13
Loop: 14
Loop: 15
Loop: 16
Loop: 17
Loop: 18
Loop: 19
Loop: 1A
Loop: 1B
Loop: 1C
Loop: 1D
Loop: 1E
Loop: 1F
Loop: 20

📌 `x86` Assembly Program

While the overall logic of our loop programs are similar, several key differences set x86_64 apart from AArch64.

Overall Differences

The first difference is in register naming and constants.

Aarch64: Registers are named as x0, x1, …, and constants are used without a special prefix.
x86: Registers have names like %rax, %rdi, %rsi, etc., and constants are prefixed with $.

Memory addressing is also different.

Aarch64: We use adr.
x86: We use the lea (load effective address) instruction combined with %rip.

Syscall is different.

Aarch64: The syscall is invoked with svc 0.
x86: We use the syscall instruction.

There are only other differences in division and arithmetic logic which you will see in the code.

Modifying for `x86`

cd ~/spo600/examples/hello/assembler/x86_64

In this directory, you'll find two assembly source files: hello-gas.s using GNU Assembly syntax (GAS) and hello-nasm.s using the NASM syntax. We'll work with the GAS syntax version since it's more consistent with what we used for AArch64.

☑️ Basic Loop Template

.text
 .globl    _start

 min = 0                         /* starting value for the loop index */
 max = 5                         /* loop exits when the index hits this number */

 _start:
     mov     $min,%r15           /* loop index */

 loop:
     /* ... body of the loop ... do something useful here ... */

     inc     %r15                /* increment the loop index */
     cmp     $max,%r15           /* see if we've hit the max */
     jne     loop                /* if not, then continue the loop */

     mov     $0,%rdi             /* set exit status to 0 */
     mov     $60,%rax            /* exit is syscall #60 */
     syscall                     /* invoke syscall */

Some differences from AArch64:

The direction in mov instructions is reversed (destination first)
We use inc for incrementing instead of add
We use jne (jump if not equal) instead of b.ne

☑️ Print Loop

.data
 msg: .ascii "Loop\n"
 len = .-msg

 .text
 .globl    _start

 min = 0                         /* starting value for the loop index */
 max = 6                         /* loop exits when the index hits this number */

 _start:
     mov     $min,%r15           /* loop index */

 loop:
     mov     $1, %rax   /* syscall: write */
     mov     $1, %rdi   /* File descriptor: stdout */
     lea     msg(%rip), %rsi /* Message address */
     mov     $len, %rdx /* Message length */
     syscall            /* Invoke syscall */

     inc     %r15                /* increment the loop index */
     cmp     $max,%r15           /* see if we've hit the max */
     jne     loop                /* if not, then continue the loop */

     mov     $0,%rdi             /* set exit status to 0 */
     mov     $60,%rax            /* exit is syscall #60 */
     syscall                     /* invoke syscall */

The lea instruction is used to load the address of msg into the %rsi register. The (%rip) part is relative addressing from the current instruction pointer.

The registers used are different!

%rax holds the syscall number (1 for write)
%rdi holds the first argument (file descriptor: 1 for stdout)
%rsi holds the second argument (message address)
%rdx holds the third argument (message length)

If you run the code with make and ./hello-gas, you should see it printing Loop 6 times as intended.

☑️ Print Loop and Index Number

.data
 msg: .ascii "Loop   \n"
 len = .-msg

 .text
 .globl    _start

 min = 0                         /* starting value for the loop index */
 max = 6                         /* loop exits when the index hits this number */

 _start:
     mov     $min,%r15           /* loop index */

 loop:
     mov        %r15, %rax
     mov        $10, %r10
     xor        %rdx, %rdx
     div        %r10            /* quotient is stored in %rax, remainder in %rdx */

     # Convert digits to ASCII
     add     $'0', %al
     add     $'0', %dl

     lea        msg(%rip), %rsi /* Message address */
     movb    %al, 5(%rsi)   /* Store tens digit in the 6th position of msg */
     movb    %dl, 6(%rsi)    /* Store units digit in the 7th position of msg */

     mov        $1, %rax   /* syscall: write */
     mov        $1, %rdi   /* File descriptor: stdout */
     mov        $len, %rdx /* Message length */
     syscall            /* Invoke syscall */

     inc     %r15                /* increment the loop index */
     cmp     $max,%r15           /* see if we've hit the max */
     jne     loop                /* if not, then continue the loop */

     mov     $0,%rdi             /* set exit status to 0 */
     mov     $60,%rax            /* exit is syscall #60 */
     syscall                     /* invoke syscall */

Here we're using different instructions for arithmetic:

We first copy the loop counter from %r15 to %rax
The xor %rdx, %rdx instruction clears the %rdx register
The div %r10 instruction divides the combined 128-bit value in %rdx:%rax by the value in %r10 (which is 10)
After division, %rax contains the quotient and %rdx contains the remainder
%al refers to the lower 8 bits of %rax, and %dl refers to the lower 8 bits of %rdx
movb instruction moves a single byte to memory

☑️ Loop From 00 - 32

.data
 msg: .ascii "Loop   \n"
 len = .-msg

 .text
 .globl    _start

 min = 0                         /* starting value for the loop index */
 max = 33                        /* loop exits when the index hits this number */

 _start:
     mov     $min,%r15           /* loop index */

 loop:
     mov        %r15, %rax
     mov        $10, %r10
     xor        %rdx, %rdx
     div        %r10            /* quotient is stored in %rax, remainder in %rdx */

     # Convert digits to ASCII
     add     $'0', %al
     add     $'0', %dl

     lea        msg(%rip), %rsi /* Message address */
     movb    %al, 5(%rsi)   /* Store tens digit in the 6th position of msg */
     movb    %dl, 6(%rsi)    /* Store units digit in the 7th position of msg */

     mov        $1, %rax   /* syscall: write */
     mov        $1, %rdi   /* File descriptor: stdout */
     mov        $len, %rdx /* Message length */
     syscall            /* Invoke syscall */

     inc     %r15                /* increment the loop index */
     cmp     $max,%r15           /* see if we've hit the max */
     jne     loop                /* if not, then continue the loop */

     mov     $0,%rdi             /* set exit status to 0 */
     mov     $60,%rax            /* exit is syscall #60 */
     syscall                     /* invoke syscall */

The only change here is to set max = 33.

☑️ Loop Without Trailing Zeros

.data
 msg: .ascii "Loop   \n"
 len = .-msg

 .text
 .globl    _start

 min = 0                         /* starting value for the loop index */
 max = 33                        /* loop exits when the index hits this number */

 _start:
     mov     $min,%r15           /* loop index */

 loop:
     mov        %r15, %rax
     mov        $10, %r10
     xor        %rdx, %rdx
     div        %r10            /* quotient is stored in %rax, remainder in %rdx */

     # Convert digits to ASCII
     add        $'0', %al
     add        $'0', %dl

     cmp        $'0', %al
     lea        msg(%rip), %rsi /* Message address */
     je         single_digit

     movb       %al, 5(%rsi)   /* Store tens digit in the 6th position of msg */
     movb       %dl, 6(%rsi)    /* Store units digit in the 7th position of msg */
     jmp        print

single_digit:
     movb       %dl, 5(%rsi)   /* Store units digit in the 6th position of msg */
     movb       $' ', 6(%rsi)    /* Store space in the 7th position of msg */

print:
     mov        $1, %rax   /* syscall: write */
     mov        $1, %rdi   /* File descriptor: stdout */
     mov        $len, %rdx /* Message length */
     syscall            /* Invoke syscall */

     inc     %r15                /* increment the loop index */
     cmp     $max,%r15           /* see if we've hit the max */
     jne     loop                /* if not, then continue the loop */

     mov     $0,%rdi             /* set exit status to 0 */
     mov     $60,%rax            /* exit is syscall #60 */
     syscall                     /* invoke syscall */

Key changes:

We compare the tens digit (%al) with ASCII '0'
If equal (je), we jump to the single_digit label
For single-digit numbers, we display only the ones digit followed by a space
We use jmp print to skip the single-digit handling code for two-digit numbers

☑️ Loop with Hex Output (0 - 20)

.data
 msg: .ascii "Loop   \n"
 len = .-msg

 .text
 .globl    _start

 min = 0                         /* starting value for the loop index */
 max = 0x21                      /* loop exits when the index hits this number */

 _start:
     mov     $min,%r15           /* loop index */

 loop:
     mov        %r15, %rax
     mov        $16, %r10
     xor        %rdx, %rdx
     div        %r10            /* quotient is stored in %rax, remainder in %rdx */

     cmp        $9, %al
     jg         convert_letter_l
     add        $'0', %al
     jmp        right_digit

convert_letter_l:
     sub        $10, %al
     add        $'A', %al

right_digit:
     cmp        $9, %dl
     jg         convert_letter_r
     add        $'0', %dl
     jmp        store_num

convert_letter_r:
     sub        $10, %dl
     add        $'A', %dl

store_num:
     lea     msg(%rip), %rsi
     movb    %al, 5(%rsi)
     movb    %dl, 6(%rsi)

print:
     mov        $1, %rax   /* syscall: write */
     mov        $1, %rdi   /* File descriptor: stdout */
     mov        $len, %rdx /* Message length */
     syscall            /* Invoke syscall */

     inc     %r15                /* increment the loop index */
     cmp     $max,%r15           /* see if we've hit the max */
     jne     loop                /* if not, then continue the loop */

     mov     $0,%rdi             /* set exit status to 0 */
     mov     $60,%rax            /* exit is syscall #60 */
     syscall                     /* invoke syscall */

Final Thoughts

This lab helped me understand and code more in modern assembly language. I got used to multiple logic concepts from memory manipulation, loops to character encoding! This helped me solidify my understanding.

One major takeaway is how explicit everything is in assembly. Every character printed and every loop iteration must be carefully crafted. I became fully aware that this is the low-level assembly and there is not BTS. I had to manage my own memory locations and be cautious with my index counters. It is far more low level than C!

Thank you for your time. See you soon! 😄

DEV Community: Juro Zaw

Queues - DSA Notes 📝

🎯 Learning Goals

🧠 Key Concepts (aka My Notes)

Enqueue

Dequeue

⌚ Time Complexities

💪 LeetCode Problems

Doubly Linked Lists - DSA Notes 📝

🎯 Learning Goals

🧠 Key Concepts (aka My Notes)

Insertion at End

Deletion at End

Access

⌚ Time Complexities

💪 LeetCode Problems

Singly Linked Lists - DSA Notes 📝

🎯 Learning Goals

🧠 Key Concepts (aka My Notes)

What is a ListNode?

Traversal

Insertion

Deletion

⌚ Time Complexities

💪 LeetCode Problems

Stacks - DSA Notes 📝

🎯 Learning Goals

🧠 Key Concepts (aka My Notes)

Stacks

Push

Push

Peek

⌚ Time Complexity for Stacks

💪 LeetCode Problems

Dynamic Arrays - DSA Notes 📝

🎯 Learning Goal

🧠 Key Concepts (aka My Notes)

Dynamic Arrays

Insertion at end (Pushing)

Resizing

🤔 Analyzing Time Complexity

⌚ Time Complexity for Dynamic Arrays

💪 LeetCode Problems

Static Arrays - DSA Notes 📝

Introduction

🎯 Learning Goal

🧠 Key Concepts (aka My Notes)

Static Arrays

Reading

Traversing

Deleting

Deleting from End of Array

Deleting at ith index

Insertion

Inserting at the End of Array

Inserting at the ith index

⌚ Time Complexity

💪 LeetCode Problems

Tidy & Wrap Up - Project Stage 03

Introduction

Debugging the AArch64 Segmentation Issue

Guaranteeing Prune Output for Every Function

Creating Test Cases

Test Case Results

x86 NOPRUNE Build

x86 PRUNE Build

AArch64 NOPRUNE Build

AArch64 PRUNE Build

Source Code

Conclusion

6502 Program Lab - Lab 3

Introduction

📌 Setup & ROM Routines

📌 Random Number Generation

📌 Welcome Message!

📌 The Main Game Loop

📌 Feedback: Higher or Lower

📌 Track Attempts

📌 Lose State

📌 Win State

What is a `ListNode`?

Deleting at `ith` index

Inserting at the `ith` index

👉 Issue 2: Fix Clone Comparison in `execute()`

📌 How about `AArch64`?

📌 Pseudocode for `execute()`

📌 `is_clone_function`: Check for a Clone

📌 `collect_function_statements`: Collect Function Statements

📌 `compare_functions`: Compare Functions

📌 `print_prune_decision`: Print Decision

📌 `execute()`

`test.c` file

📌 `AArch64` Assembly Program

Modifying the `AArch64` Assembly Program

📌 `x86` Assembly Program

Modifying for `x86`