DEV Community: JP

SPO600 Project Stage 3: Wrapping it Up

JP — Thu, 17 Apr 2025 18:43:21 +0000

Introduction

Welcome back! These are the goals for the final installment of the SPO600 Project:

The pass must identify 2+ versions of a cloned function.
Create a test case that provides a “PRUNE” or “NO PRUNE” recommendation.
Refactor and clean up the Stage 2 implementation.

Note: here’s the GitHub repo containing the test cases for and stage 3 implementation.

Finding Multiple Function Versions of a Cloned Function

The current implementation has access to all variants via call graph but only records the “fingerprint” of a single variant.

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc

...

// Compare variable reference maps
**auto orig_map_iter = gimple_var_map_1.begin();
auto clone_map_iter = gimple_var_map_2.begin();**

while (orig_map_iter != gimple_var_map_1.end())
{
    if (orig_map_iter->first != clone_map_iter->first || orig_map_iter->second != clone_map_iter->second)
    {
        return false;
    }
    ++orig_map_iter;
    ++clone_map_iter;
}

Creating a Function “Fingerprint”

A fingerprint is unique to each person and can be used to identify a person. It can work in a similar way for functions, where the number of basic blocks, statements, and operations can identify the structure of a variant.

This approach must be approached with caution, as there is an increased risk of false positives for both “PRUNE” and “NO PRUNE” cases (Spoiler: I ran into that issue during refactoring).

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc
namespace
{

 struct FunctionFingerPrint
    {
        int bb_count = 0;
        int stmt_count = 0;
        std::vector<enum gimple_code> gimple_ops;
        std::vector<unsigned> ops_count;
        std::vector<enum tree_code> op_types;
        std::map<int, int> mapped_ids;
    };

...

Recording a Function “Fingerprint”

Multiple variants can be stored in a map data structure where the variant name is the key and the function “Fingerprint” is the corresponding value.

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc
namespace
{

...

 class pass_prune_clones : public gimple_opt_pass
    {
    public:
        pass_prune_clones(gcc::context *ctxt)
            : gimple_opt_pass({GIMPLE_PASS,
                               "prune_clones",
                               OPTGROUP_NONE,
                               TV_NONE,
                               PROP_cfg,
                               0, 0, 0, 0},
                              ctxt) {}

        bool gate(function *) override { return true; }
        unsigned int execute(function *func) override;

    private:
        static bool get_base;
        **static std::map<std::string, FunctionFingerPrint> fingerprints;**
    };

...

Recording the function stays the same from stage 2, but refactored into a GimpleVarMapper class.

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc
namespace 
{

...

    class GimpleVarMapper
    {
    public:
        int getGimpleVars(std::map<tree, int> &resolver_map, int index, gimple *stmt, std::map<int, int> &compare_map)
        {
            std::vector<tree> gimple_vars;

            switch (gimple_code(stmt))
            {
            case GIMPLE_ASSIGN:
            {
                tree lhs = gimple_assign_lhs(stmt);
                gimple_vars.push_back(lhs);
                int rhs_ops = gimple_num_ops(stmt) - 1;
                for (int i = 1; i <= rhs_ops; ++i)
                    gimple_vars.push_back(gimple_op(stmt, i));
                break;
            }
            case GIMPLE_DEBUG_BIND:
            {
                if (tree var = gimple_debug_bind_get_var(stmt))
                    gimple_vars.push_back(var);
                if (tree val = gimple_debug_bind_get_value(stmt))
                    gimple_vars.push_back(val);
                break;
            }
            case GIMPLE_COND:
            {
                if (tree lhs = gimple_cond_lhs(stmt))
                    gimple_vars.push_back(lhs);
                if (tree rhs = gimple_cond_rhs(stmt))
                    gimple_vars.push_back(rhs);
                break;
            }
            case GIMPLE_CALL:
            {
                if (tree lhs = gimple_call_lhs(stmt))
                    gimple_vars.push_back(lhs);
                break;
            }
            default:
                break;
            }

            for (tree var : gimple_vars)
            {
                if (resolver_map.find(var) != resolver_map.end())
                {
                    compare_map[index] = resolver_map[var];
                }
                else
                {
                    resolver_map[var] = index;
                    compare_map[index] = index;
                }
                ++index;
            }

            return index;
        }
    };

    ...

Once the base function is recorded, the variants are fingerprinted and compared to the base function’s fingerprint. A boolean value is returned, corresponding to a “PRUNE” or “NO PRUNE” recommendation made in pass_prune_clones::execute.

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc
namespace 
{

...

    class CloneComparator
    {
    public:
        bool compare(const FunctionFingerPrint &resolver_map, function *func)
        {
            FunctionFingerPrint curr_fingerprint;
            std::map<tree, int> curr_resolver_map;
            std::map<int, int> curr_ids;
            int index = 0;

            basic_block bb;
            FOR_EACH_BB_FN(bb, func)
            {
                curr_fingerprint.bb_count++;
                for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
                {
                    curr_fingerprint.stmt_count++;
                }
            }

            if (curr_fingerprint.bb_count != resolver_map.bb_count || curr_fingerprint.stmt_count != resolver_map.stmt_count)
                return false;

            auto gop = resolver_map.gimple_ops.begin();
            auto opc = resolver_map.ops_count.begin();
            auto ot = resolver_map.op_types.begin();

            GimpleVarMapper varMapper;

            FOR_EACH_BB_FN(bb, func)
            {
                for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
                {
                    gimple *stmt = gsi_stmt(gsi);
                    index = varMapper.getGimpleVars(curr_resolver_map, index, stmt, curr_ids);

                    if (gimple_code(stmt) != *gop || gimple_num_ops(stmt) != *opc)
                        return false;

                    if (*gop == GIMPLE_ASSIGN && *(ot++) != gimple_assign_rhs_code(stmt))
                        return false;

                    ++gop;
                    ++opc;
                }
            }

            return resolver_map.mapped_ids == curr_ids;
        }
    };

...

 class pass_prune_clones : public gimple_opt_pass
    {
        unsigned int pass_prune_clones::execute(function *func)
        {
                 **CloneComparator comparator;
                    if (comparator.compare(resolver_map, func))
                    {
                        fprintf(dump_file, "[ PRUNE ]: %s\n", name.c_str());
                    }
                    else
                    {
                        fprintf(dump_file, "[ NO PRUNE ]: %s\n", name.c_str());
                    }

...**

Ta-da! The pass now has the ability to make a “PRUNE” or “NO PRUNE” recommendation on each variant. We’ll confirm the functionality in the “Results” section.

Test Cases

One of the new tests was inspired by the original test case provided by Chris Tyler - where it uses a “for” loop to scale an int16 value and converts it into an int32 value then back to int16.

//~/spo600/examples/test-clone/clone-test-core.c

// Original
CLONE_ATTRIBUTE
void scale_samples(int16_t *in, int16_t *out, int cnt, int volume) {
    for (int x = 0; x < cnt; x++) {
        out[x] = ((((int32_t) in[x]) * ((int32_t)(32767 * volume / 100) << 1)) >> 16);
    }
}

Unrolling 4 Units

This test was inspired by one of the 6502 optimization techniques - loop unrolling. This test combines both vectorization and arithmetic test cases.

// Slightly modified - unrolling 4 units
CLONE_ATTRIBUTE
void scale_samples_alt(int16_t *in, int16_t *out, int cnt, int volume) {
    int32_t factor = ((int32_t)(32767 * volume / 100) << 1);
    for (int x = 0; x < cnt; x += 4) {
        for (int j = 0; j < 4 && x + j < cnt; j++) {
            out[x + j] = (((int32_t) in[x + j]) * factor) >> 16;
        }
    }
}

The original test case used a “for” loop, processing a single unit at a time. With unrolling, it processes a “packet” of 4 units at a time. It accomplishes the same task but as seen in 6502, unrolling reduces the number of branches and loop counters.

This structural difference makes the function more focused on vectorization, and it’s likely to be preserved by clone detection as a unique variant, rather than pruned.

Arithmetic Operation

This test case is rather simple, where 2 int values are added via pointers.

// Scaler operation
CLONE_ATTRIBUTE
void scalar_op(int *a, int *b) {
    *a += *b;
}

This test can be considered a baseline to verify whether the pruning pass can distinguish between simple scalar operations and more complex, vectorizable variants like the previous case.

Performing the Tests

The directory with the original test was cloned:

cd ~/spo600/examples
cp -r ./test-clone ./test-clone-2

Insert the test cases in clone-test-core.c

// ~/spo600/examples/test-clone-2/clone-test-core.c

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include "vol.h"

int sum_sample(int16_t *buff, size_t samples) {
    int sum = 0;
    for (size_t i = 0; i < samples; i++) {
        sum += buff[i];
    }
    return sum;
}

// Original
CLONE_ATTRIBUTE
void scale_samples(int16_t *in, int16_t *out, int cnt, int volume) {
    for (int x = 0; x < cnt; x++) {
        out[x] = ((((int32_t) in[x]) * ((int32_t)(32767 * volume / 100) << 1)) >> 16);
    }
}

**// Slightly modified - unrolling 4 units
CLONE_ATTRIBUTE
void scale_samples_alt(int16_t *in, int16_t *out, int cnt, int volume) {
    int32_t factor = ((int32_t)(32767 * volume / 100) << 1);
    for (int x = 0; x < cnt; x += 4) {
        for (int j = 0; j < 4 && x + j < cnt; j++) {
            out[x + j] = (((int32_t) in[x + j]) * factor) >> 16;
        }
    }
}

// Scaler operation
CLONE_ATTRIBUTE
void scalar_op(int *a, int *b) {
    *a += *b;
}**

int main(int argc, char **argv) {
    int16_t *in = (int16_t *)calloc(SAMPLES, sizeof(int16_t));
    int16_t *out = (int16_t *)calloc(SAMPLES, sizeof(int16_t));
    int a = 1;
    int b = 2;

    vol_createsample(in, SAMPLES);

    if (argc > 1 && argv[1][0] == 'a') {
        scale_samples_alt(in, out, SAMPLES, VOLUME);
    scalar_op(&a, &b);
    } else {
        scale_samples(in, out, SAMPLES, VOLUME);
    scalar_op(&a, &b);
    }

    int ttl = sum_sample(out, SAMPLES);
    printf("Result: %d\n", ttl);

    free(in);
    free(out);
    return 0;
}

Uncomment DUMP_ALL = 1
Use the built gcc with the prune_clones pass
1. PATH="$HOME/gcc-test-002/bin:$PATH"
  1. Note: use your gcc directory
Run command make all to generate the dump files
1. Contains the “PRUNE” or “NO PRUNE” log.

Results

And the results!

// x86

japablo@x86-001:~/spo600/examples/test-clone-2$ grep -i "PRUNE" clone-test-x86-*
**clone-test-x86-noprune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scalar_op.arch_x86_64_v3
clone-test-x86-noprune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scale_samples_alt.arch_x86_64_v3**
clone-test-x86-noprune-clone-test-core.c.264t.prune_clones:[ NO PRUNE ]: scale_samples.arch_x86_64_v3
clone-test-x86-prune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scalar_op.popcnt
clone-test-x86-prune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scale_samples_alt.popcnt
clone-test-x86-prune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scale_samples.popcnt

// aarch64
[japablo@aarch64-002 test-clone]$ grep -i "PRUNE" clone-test-aarch64-*
clone-test-aarch64-noprune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scalar_op.sve2
clone-test-aarch64-noprune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scalar_op.fp
**clone-test-aarch64-noprune-clone-test-core.c.264t.prune_clones:[ NO PRUNE ]: scale_samples_alt.sve2**
clone-test-aarch64-noprune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scale_samples_alt.fp
clone-test-aarch64-noprune-clone-test-core.c.264t.prune_clones:[ NO PRUNE ]: scale_samples.sve2
clone-test-aarch64-noprune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scale_samples.fp
clone-test-aarch64-prune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scalar_op.sve2
clone-test-aarch64-prune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scalar_op.fp
clone-test-aarch64-prune-clone-test-core.c.264t.prune_clones:[ NO PRUNE ]: scale_samples_alt.sve2
clone-test-aarch64-prune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scale_samples_alt.fp
clone-test-aarch64-prune-clone-test-core.c.264t.prune_clones:[ NO PRUNE ]: scale_samples.sve2
clone-test-aarch64-prune-clone-test-core.c.264t.prune_clones:[ PRUNE ]: scale_samples.fp

Note: I added sve2 and fp when compiling in aarch64.

Discussion

Looking at the results, there are some false positives, where it recommends “PRUNE” when it should not, and false negatives, where it recommends “NO PRUNE” when it should. This can be attributed to the level of specificity in how a function is fingerprinted.

When refactoring, I tried normalizing SSA names and expressions, but the implementation ended up being too aggressive—treating variables with different origins, like parameters, constants, or intermediate results, as the same. That led to a higher false positive rate.

Limitations

1.Assumption of Same Control Flow for Comparison

The fingerprint comparison assumes that the control flow structure (basic blocks, statements) of the functions will be identical if they are clones. However, optimizations like reordering of basic blocks or merging of identical blocks could cause differences in control flow that don't impact the semantic behavior of the program. This could lead to false negatives where a valid clone is not pruned.

2. Hard-Coded Assumptions in Function Name Processing

The code assumes that the function name always contains a ".resolver" suffix to indicate whether a function is a resolver. This is a somewhat brittle approach, as the naming conventions could change, leading to incorrect behavior. Additionally, the method for extracting the base function name from the full name (name.substr(0, name.find("."))) may fail in edge cases, such as when function names multiple dots.

3. Potential for Incorrect Handling of Debugging Information

The GIMPLE_DEBUG_BIND operation is considered during SSA variable resolution, but debugging information may not always be included in actual program behavior, leading to the inclusion of irrelevant variables during the comparison. This could affect the accuracy of the pruning process.

Conclusion

Overall, this project was challenging—not just in theory, but especially in practice. Actually coding, testing each idea, and going through countless GCC builds taught me way more than just reading about it ever could. While the implementation isn’t perfect, it’s something I never would’ve attempted—or even understood—just four months ago. I had zero knowledge of this back then, so I’m really proud I was able to get it done!

SPO600 Project Stage 2, Part 3: “Prune Away!”

JP — Sun, 06 Apr 2025 03:16:51 +0000

Introduction

Welcome back for the final part of stage 2, printing a “prune” suggestion in the dump file. Each function can be identified by its “fingerprint”, all we need to do is compare them and print a suggestion to prune or not. Let’s get started!

Comparing Function Fingerprints

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc

std::string base_function;
        int gimple_bb_count_1 = 0;
        int gimple_stmt_count_1 = 0;
        std::vector<enum gimple_code> gimple_sequence_1;
        std::vector<unsigned> gimple_ops_count_1;
        std::vector<enum tree_code> gimple_op_types_1;
        std::map<int, int> gimple_var_map_1;
...

bool pass_prune_clones::compare_function_info(function *func) const
{
    int bb_count = 0;
    int stmt_count = 0;
    basic_block bb;
    int i = 0;
    std::map<tree, int> first_occurrence_map;
    std::map<int, int> gimple_var_map_2;

    FOR_EACH_BB_FN(bb, func)
    {
        bb_count++;
        for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
        {
            stmt_count++;
            i = get_gimple_vars(first_occurrence_map, i, gsi_stmt(gsi), gimple_var_map_2);
        }
    }

    if (bb_count != gimple_bb_count_1)
    {
        fprintf(dump_file, "[DIFF] BB count: %d vs %d\n",
                bb_count, gimple_bb_count_1);
        return false;
    }

    if (stmt_count != gimple_stmt_count_1)
    {
        fprintf(dump_file, "[DIFF] Statement count: %d vs %d\n",
                stmt_count, gimple_stmt_count_1);
        return false;
    }

    if (bb_count != gimple_bb_count_1 || stmt_count != gimple_stmt_count_1)
    {
        return false;
    }

    auto it = gimple_sequence_1.begin();
    auto count_it = gimple_ops_count_1.begin();
    auto optype_it = gimple_op_types_1.begin();

    FOR_EACH_BB_FN(bb, func)
    {
        for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
        {
            if (gimple_code(gsi_stmt(gsi)) != *it || gimple_num_ops(gsi_stmt(gsi)) != *count_it)
            {
                return false;
            }
            if (*it == GIMPLE_ASSIGN && *(optype_it++) != gimple_assign_rhs_code(gsi_stmt(gsi)))
            {
                return false;
            }
            ++it;
            ++count_it;
        }
    }

    // Compare variable reference maps
    auto orig_map_iter = gimple_var_map_1.begin();
    auto clone_map_iter = gimple_var_map_2.begin();
    while (orig_map_iter != gimple_var_map_1.end())
    {
        if (orig_map_iter->first != clone_map_iter->first || orig_map_iter->second != clone_map_iter->second)
        {
            return false;
        }
        ++orig_map_iter;
        ++clone_map_iter;
    }

    return true;
}

1. traverse every basic block in the function using FOR_EACH_BB_FN, and count:

The number of basic blocks (bb_count)
The number of statements (stmt_count)

We also regenerate a variable usage map (gimple_var_map_2) by calling get_gimple_vars(...) on each statement. This tracks how and where each variable is used, without caring about their actual names.

2. Compare Block & Statement Counts


if (bb_count != gimple_bb_count_1 || stmt_count != gimple_stmt_count_1)

Before diving into deep comparison, we check if the raw shape of the functions match:

Same number of basic blocks?
Same number of GIMPLE statements?

If these are different, we conclude early — the functions are structured differently.

3. Compare GIMPLE Statement Patterns

We iterate through each basic block and each GIMPLE statement, comparing the overall structure:

The type of GIMPLE statement (e.g., GIMPLE_ASSIGN, GIMPLE_CALL, etc.)
The number of operands in the statement
And if it’s an assignment, we go deeper:
- We compare the operation type used on the RHS (right-hand side).

These checks ensure that both functions are doing the same operations in the same order, even if the variable names (LHS/RHS identifiers) are different.

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc
...
gimple_sequence_2.push_back(gimple_code(stmt));
gimple_ops_count_2.push_back(gimple_num_ops(stmt));

if (is_gimple_assign(stmt))
{
    gimple_op_types_2.push_back(gimple_assign_rhs_code(stmt));
}

gimple_code(stmt) tells you what type of statement it is (GIMPLE_ASSIGN, GIMPLE_CALL, etc.)
gimple_num_ops(stmt) tells you how many operands it uses
gimple_assign_rhs_code(stmt) is the key one — it gives you the specific opcode on the RHS

4. Compare Variable Usage Roles

The final and most subtle comparison:

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc
if (orig_map_iter->first != clone_map_iter->first || orig_map_iter->second != clone_map_iter->second)

We compare the normalized variable usage maps (gimple_var_map_1 vs. gimple_var_map_2). These maps tell us things like:

“The second statement uses the same variable as the one first used in statement X.”

If the maps are identical, that means the variables play the same roles in both functions, even if their names are completely different.

Putting it all Together

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc
#include <vector>
#include <string>
#include <map>
#include <stdlib.h>

#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"
#include "cgraph.h"
#include "gimple-ssa.h"
#include "attribs.h"
#include "pretty-print.h"
#include "tree-inline.h"
#include "intl.h"
#include "function.h"
#include "basic-block.h"

namespace
{
    const pass_data prune_clones_pass_data = {
        GIMPLE_PASS,    /* type */
        "prune_clones", /* name */
        OPTGROUP_NONE,  /* optinfo_flags */
        TV_NONE,        /* tv_id */
        PROP_cfg,
        0,
        0,
        0,
        0,
    };

    class pass_prune_clones : public gimple_opt_pass
    {
    public:
        pass_prune_clones(gcc::context *ctxt)
            : gimple_opt_pass(prune_clones_pass_data, ctxt) {}

        bool gate(function *) final override { return true; }
        void set_pass_param(unsigned int, bool) override {}
        unsigned int execute(function *) final override;

    private:
        int get_gimple_vars(std::map<tree, int> &first_occurrence_map, int i, gimple *stmt, std::map<int, int> &out_map) const;
        bool is_base_function(const std::string &name) const;
        void record_function_info(function *func);
        bool compare_function_info(function *func) const;

        std::string base_function;
        int gimple_bb_count_1 = 0;
        int gimple_stmt_count_1 = 0;
        std::vector<enum gimple_code> gimple_sequence_1;
        std::vector<unsigned> gimple_ops_count_1;
        std::vector<enum tree_code> gimple_op_types_1;
        std::map<int, int> gimple_var_map_1;
    };

    int pass_prune_clones::get_gimple_vars(std::map<tree, int> &first_occurrence_map, int i, gimple *stmt, std::map<int, int> &out_map) const
    {
        std::vector<tree> vars;

        switch (gimple_code(stmt))
        {

        case GIMPLE_COND:
        {
            tree left_op = gimple_cond_lhs(stmt);
            tree right_op = gimple_cond_rhs(stmt);
            if (left_op)
                vars.push_back(left_op);
            if (right_op)
                vars.push_back(right_op);
            break;
        }

        case GIMPLE_CALL:
        {
            tree left_op = gimple_call_lhs(stmt);
            if (left_op)
                vars.push_back(left_op);
            break;
        }

        case GIMPLE_ASSIGN:
        {
            tree left_op = gimple_assign_lhs(stmt);
            vars.push_back(left_op);

            int rhs_ops = gimple_num_ops(stmt) - 1;
            for (int i = 1; i <= rhs_ops; ++i)
            {
                tree op = gimple_op(stmt, i);
                vars.push_back(op);
            }
            break;
        }

        case GIMPLE_DEBUG_BIND:
        {
            tree debug_var = gimple_debug_bind_get_var(stmt);
            tree debug_value = gimple_debug_bind_get_value(stmt);
            if (debug_var)
                vars.push_back(debug_var);
            if (debug_value)
                vars.push_back(debug_value);
            break;
        }

        default:
            break;
        }

        for (tree debug_var : vars)
        {
            std::map<tree, int>::iterator it = first_occurrence_map.find(debug_var);

            if (it != first_occurrence_map.end())
            {
                out_map[i] = it->second;
            }
            else
            {
                first_occurrence_map[debug_var] = i;
                out_map[i] = i;
            }

            ++i;
        }

        return i;
    }

    bool pass_prune_clones::is_base_function(const std::string &name) const
    {
        return name.find(base_function) == 0 && name.find(".resolver") == std::string::npos;
    }

    void pass_prune_clones::record_function_info(function *func)
    {
        basic_block bb;
        int i = 0;
        std::map<tree, int> first_occurrence_map;

        FOR_EACH_BB_FN(bb, func)
        {
            gimple_bb_count_1++;
            for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
            {
                gimple_stmt_count_1++;
                i = get_gimple_vars(first_occurrence_map, i, gsi_stmt(gsi), gimple_var_map_1);
                gimple_sequence_1.push_back(gimple_code(gsi_stmt(gsi)));
                gimple_ops_count_1.push_back(gimple_num_ops(gsi_stmt(gsi)));
                if (is_gimple_assign(gsi_stmt(gsi)))
                {
                    gimple_op_types_1.push_back(gimple_assign_rhs_code(gsi_stmt(gsi)));
                }
            }
        }
    }

    bool pass_prune_clones::compare_function_info(function *func) const
    {
        int bb_count = 0;
        int stmt_count = 0;
        basic_block bb;
        int i = 0;
        std::map<tree, int> first_occurrence_map;
        std::map<int, int> gimple_var_map_2;

        FOR_EACH_BB_FN(bb, func)
        {
            bb_count++;
            for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
            {
                stmt_count++;
                i = get_gimple_vars(first_occurrence_map, i, gsi_stmt(gsi), gimple_var_map_2);
            }
        }

        if (bb_count != gimple_bb_count_1)
        {
            fprintf(dump_file, "[DIFF] BB count: %d vs %d\n",
                    bb_count, gimple_bb_count_1);
            return false;
        }

        if (stmt_count != gimple_stmt_count_1)
        {
            fprintf(dump_file, "[DIFF] Statement count: %d vs %d\n",
                    stmt_count, gimple_stmt_count_1);
            return false;
        }

        if (bb_count != gimple_bb_count_1 || stmt_count != gimple_stmt_count_1)
        {
            return false;
        }

        auto it = gimple_sequence_1.begin();
        auto count_it = gimple_ops_count_1.begin();
        auto optype_it = gimple_op_types_1.begin();

        FOR_EACH_BB_FN(bb, func)
        {
            for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
            {
                if (gimple_code(gsi_stmt(gsi)) != *it || gimple_num_ops(gsi_stmt(gsi)) != *count_it)
                {
                    return false;
                }
                if (*it == GIMPLE_ASSIGN && *(optype_it++) != gimple_assign_rhs_code(gsi_stmt(gsi)))
                {
                    return false;
                }
                ++it;
                ++count_it;
            }
        }

        // Compare variable reference maps
        auto orig_map_iter = gimple_var_map_1.begin();
        auto clone_map_iter = gimple_var_map_2.begin();
        while (orig_map_iter != gimple_var_map_1.end())
        {
            if (orig_map_iter->first != clone_map_iter->first || orig_map_iter->second != clone_map_iter->second)
            {
                return false;
            }
            ++orig_map_iter;
            ++clone_map_iter;
        }

        return true;
    }

    unsigned int pass_prune_clones::execute(function *func)
    {
        if (!dump_file || !func || !func->cfg)
            return 0;

        struct cgraph_node *node = cgraph_node::get(func->decl);
        if (!node)
        {
            fprintf(dump_file, "ERROR: cgraph_node::get(func->decl)\n");
            return 0;
        }

        const std::string name(node->name());
        if (base_function.empty() && name.find(".resolver") != std::string::npos)
        {
            base_function = name.substr(0, name.find(".resolver"));
            fprintf(dump_file, "[BASE] Found: %s\n", base_function.c_str());
        }

        if (!is_base_function(name))
            return 0;

        // Record info for the first matching function
        if (gimple_bb_count_1 == 0 && gimple_stmt_count_1 == 0)
        {
            record_function_info(func);
        }
        **// Compare info for cloned functions
        else if (compare_function_info(func))
        {
            fprintf(dump_file, "[PRUNE]: %s\n", base_function.c_str());
        }
        else
        {
            fprintf(dump_file, "[NO PRUNE]: %s\n", base_function.c_str());
        }**

        return 0;
    }

} // anonymous namespace

gimple_opt_pass *make_pass_prune_clones(gcc::context *ctxt)
{
    return new pass_prune_clones(ctxt);
}

The pruning suggestion is bolded in unsigned int pass_prune_clones::execute.

Results

Setup

Setup instructions can be found here

Test Results

japablo@x86-001:~/spo600/examples/test-clone$ cat clone-test-x86-noprune-clone-test-core.c.228t.prune_clones
...
;; Function scale_samples.arch_x86_64_v3 (scale_samples.arch_x86_64_v3, funcdef_no=25, decl_uid=3985, cgraph_uid=30, symbol_order=28)

[DIFF] BB count: 40 vs 31
[NO PRUNE]: 

japablo@x86-001:~/spo600/examples/test-clone$ cat clone-test-x86-prune-clone-test-core.c.228t.prune_clones
...
;; Function scale_samples.popcnt (scale_samples.popcnt, funcdef_no=25, decl_uid=3985, cgraph_uid=30, symbol_order=28)

[PRUNE]: 
__attribute__((target ("popcnt"), target_clones ("default", "popcnt")))
void scale_samples.popcnt (int16_t * in, int16_t * out, int cnt, int volume)

The respective tests show which function can be safely pruned and which ones should not be pruned!

Reflection

The bulk of the work for this stage was done in part 2. This was easier since we have the maps that “fingerprint” each function variant.

Conclusion

Time to rest my mind for a bit. Talk soon!

SPO600 Project Stage 2, Part 2: "Where Art Thou, Clones?"

JP — Sun, 06 Apr 2025 02:34:14 +0000

Introduction

I’ll keep the introduction short - welcome back! The code will be broken down into parts and explained as we go along. Let’s find those function variants!

Identifying the Function Variants

Identifying the clones require a reference point - the base function serves as the “source of truth” with its respective basic blocks, statements, control flow, etc., and becomes the template to compare against when analyzing the variants.

Identifying the Base Function

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc
...

std::string base_function;

...

unsigned int pass_prune_clones::execute(function *func)
{
    ...
    const std::string name(node->name());
  if (base_function.empty() && name.find(".resolver") != std::string::npos)
  {
      base_function = name.substr(0, name.find(".resolver"));
      fprintf(dump_file, "[BASE] Found: %s\n", base_function.c_str());
  }
}

...

bool pass_prune_clones::is_base_function(const std::string &name) const
{
    return name.find(base_function) == 0 && name.find(".resolver") == std::string::npos;
}

The first thing to do is to get the name of the function when entering the call graph. Note that the name of function can have any of the variant extensions (e.g. .constprop.0, .ssa, etc.). .resolver is the source function because ifuncs get resolved during runtime - allow multiple implementations during runtime.

pass_prune_clones::execute extracts the function name from .resolver.
pass_prune_clones::is_base_function checks if the current node is function variant by comparing it the base function name

Fingerprinting Functions

gcc documentation provides a list of accessors that simplifies the extraction inGIMPLE.

The combo of get_gimple_vars and record_function_info is being used to record a structured fingerprint of a function — not based on specific variable names, but on how it behaves structurally (e.g., statement types, number of operands, variable usage patterns).

get_gimple_vars(...) processes a single GIMPLE statement by:

Extract Variables

For GIMPLE_COND, GIMPLE_ASSIGN ,GIMPLE_CALL, and GIMPLE_DEBUG_BIND, it collects involved tree variables (like lhs/rhs, debug values) into a std::vector<tree> vars — rather than identifying variables by their names, it tracks their first occurrence and usage position for structural comparisons across different functions.
Map First Occurrence

For each variable in vars:

- If this is the **first time** it appears, it's assigned a new ID `i`.
- If it's been seen before, it reuses the same ID.

The output is stored in:

first_occurrence_map: mapping tree → ID
out_map: mapping ID of this statement → ID of first occurrence

This abstract variable names away and focusses on their role — a = b + c and x = y + z would look the same if variable roles match.

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc

...

int pass_prune_clones::get_gimple_vars(std::map<tree, int> &first_occurrence_map, int i, gimple *stmt, std::map<int, int> &out_map) const
{
    std::vector<tree> vars;

    switch (gimple_code(stmt))
    {

    case GIMPLE_COND:
    {
        tree left_op = gimple_cond_lhs(stmt);
        tree right_op = gimple_cond_rhs(stmt);
        if (left_op)
            vars.push_back(left_op);
        if (right_op)
            vars.push_back(right_op);
        break;
    }

    case GIMPLE_CALL:
    {
        tree left_op = gimple_call_lhs(stmt);
        if (left_op)
            vars.push_back(left_op);
        break;
    }

    case GIMPLE_ASSIGN:
    {
        tree left_op = gimple_assign_lhs(stmt);
        vars.push_back(left_op);

        int rhs_ops = gimple_num_ops(stmt) - 1;
        for (int i = 1; i <= rhs_ops; ++i)
        {
            tree op = gimple_op(stmt, i);
            vars.push_back(op);
        }
        break;
    }

    case GIMPLE_DEBUG_BIND:
    {
        tree debug_var = gimple_debug_bind_get_var(stmt);
        tree debug_value = gimple_debug_bind_get_value(stmt);
        if (debug_var)
            vars.push_back(debug_var);
        if (debug_value)
            vars.push_back(debug_value);
        break;
    }

    default:
        break;
    }

    for (tree debug_var : vars)
    {
        std::map<tree, int>::iterator it = first_occurrence_map.find(debug_var);

        if (it != first_occurrence_map.end())
        {
            out_map[i] = it->second;
        }
        else
        {
            first_occurrence_map[debug_var] = i;
            out_map[i] = i;
        }

        ++i;
    }

    return i;
}

Putting it Together

Finally, there’s a way to identify the base function and to fingerprint each function for comparison! Let’s put the code all together!

// ~/gccsrc/gcc/gcc/tree-prune-clones.cc
#include <vector>
#include <string>
#include <map>
#include <stdlib.h>

#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"
#include "cgraph.h"
#include "gimple-ssa.h"
#include "attribs.h"
#include "pretty-print.h"
#include "tree-inline.h"
#include "intl.h"
#include "function.h"
#include "basic-block.h"

namespace
{
    const pass_data prune_clones_pass_data = {
        GIMPLE_PASS,    /* type */
        "prune_clones", /* name */
        OPTGROUP_NONE,  /* optinfo_flags */
        TV_NONE,        /* tv_id */
        PROP_cfg,
        0,
        0,
        0,
        0,
    };

    class pass_prune_clones : public gimple_opt_pass
    {
    public:
        pass_prune_clones(gcc::context *ctxt)
            : gimple_opt_pass(prune_clones_pass_data, ctxt) {}

        bool gate(function *) final override { return true; }
        void set_pass_param(unsigned int, bool) override {}
        unsigned int execute(function *) final override;

    private:
        int get_gimple_vars(std::map<tree, int> &first_occurrence_map, int i, gimple *stmt, std::map<int, int> &out_map) const;
        bool is_base_function(const std::string &name) const;
        void record_function_info(function *func);

        std::string base_function;
        int gimple_bb_count_1 = 0;
        int gimple_stmt_count_1 = 0;
        std::vector<enum gimple_code> gimple_sequence_1;
        std::vector<unsigned> gimple_ops_count_1;
        std::vector<enum tree_code> gimple_op_types_1;
        std::map<int, int> gimple_var_map_1;
    };

    int pass_prune_clones::get_gimple_vars(std::map<tree, int> &first_occurrence_map, int i, gimple *stmt, std::map<int, int> &out_map) const
    {
        std::vector<tree> vars;

        switch (gimple_code(stmt))
        {

        case GIMPLE_COND:
        {
            tree left_op = gimple_cond_lhs(stmt);
            tree right_op = gimple_cond_rhs(stmt);
            if (left_op)
                vars.push_back(left_op);
            if (right_op)
                vars.push_back(right_op);
            break;
        }

        case GIMPLE_CALL:
        {
            tree left_op = gimple_call_lhs(stmt);
            if (left_op)
                vars.push_back(left_op);
            break;
        }

        case GIMPLE_ASSIGN:
        {
            tree left_op = gimple_assign_lhs(stmt);
            vars.push_back(left_op);

            int rhs_ops = gimple_num_ops(stmt) - 1;
            for (int i = 1; i <= rhs_ops; ++i)
            {
                tree op = gimple_op(stmt, i);
                vars.push_back(op);
            }
            break;
        }

        case GIMPLE_DEBUG_BIND:
        {
            tree debug_var = gimple_debug_bind_get_var(stmt);
            tree debug_value = gimple_debug_bind_get_value(stmt);
            if (debug_var)
                vars.push_back(debug_var);
            if (debug_value)
                vars.push_back(debug_value);
            break;
        }

        default:
            break;
        }

        for (tree debug_var : vars)
        {
            std::map<tree, int>::iterator it = first_occurrence_map.find(debug_var);

            if (it != first_occurrence_map.end())
            {
                out_map[i] = it->second;
            }
            else
            {
                first_occurrence_map[debug_var] = i;
                out_map[i] = i;
            }

            ++i;
        }

        return i;
    }

    bool pass_prune_clones::is_base_function(const std::string &name) const
    {
        return name.find(base_function) == 0 && name.find(".resolver") == std::string::npos;
    }

    void pass_prune_clones::record_function_info(function *func)
    {
        basic_block bb;
        int i = 0;
        std::map<tree, int> first_occurrence_map;

        FOR_EACH_BB_FN(bb, func)
        {
            gimple_bb_count_1++;
            for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi))
            {
                gimple_stmt_count_1++;
                i = get_gimple_vars(first_occurrence_map, i, gsi_stmt(gsi), gimple_var_map_1);
                gimple_sequence_1.push_back(gimple_code(gsi_stmt(gsi)));
                gimple_ops_count_1.push_back(gimple_num_ops(gsi_stmt(gsi)));
                if (is_gimple_assign(gsi_stmt(gsi)))
                {
                    gimple_op_types_1.push_back(gimple_assign_rhs_code(gsi_stmt(gsi)));
                }
            }
        }
    }

    unsigned int pass_prune_clones::execute(function *func)
    {
        if (!dump_file || !func || !func->cfg)
            return 0;

        struct cgraph_node *node = cgraph_node::get(func->decl);
        if (!node)
        {
            fprintf(dump_file, "ERROR: cgraph_node::get(func->decl)\n");
            return 0;
        }

        const std::string name(node->name());
        if (base_function.empty() && name.find(".resolver") != std::string::npos)
        {
            base_function = name.substr(0, name.find(".resolver"));
            fprintf(dump_file, "[BASE] Found: %s\n", base_function.c_str());
        }

        if (!is_base_function(name))
            return 0;

        // Record info for the first matching function
        if (gimple_bb_count_1 == 0 && gimple_stmt_count_1 == 0)
        {
            record_function_info(func);
        }

        return 0;
    }

} // anonymous namespace

gimple_opt_pass *make_pass_prune_clones(gcc::context *ctxt)
{
    return new pass_prune_clones(ctxt);
}

Results

The test cases were generously provided by Professor Chris Tyler.

Setup

Build gcc with the newly added pass
1. cd ~/gcc-build-002
2. time make -j$(nproc) |& tee rebuild_log.log
3. make install
cd ~
tar xvf /public/spo600-test-clone.tgz: copy the test cases into current directory
cd ~/spo600/examples/test-clone
vim Makefile and uncomment DUMP_ALL
PATH=”$HOME/gcc-test-001/bin:$PATH": set default gcc to the newly built version
make: execute test cases

Note: ls will reveal all the dumpfiles created, find the name of the pass. In my case my pass was named prune-clones.

Test Results

japablo@x86-001:~/spo600/examples/test-clone$ cat clone-test-x86-prune-clone-test-core.c.228t.prune_clones | grep "DIFF"
;; Function scale_samples.arch_x86_64_v3 (scale_samples.arch_x86_64_v3, funcdef_no=25, decl_uid=3985, cgraph_uid=30, symbol_order=28)
[DIFF] BB count: 40 vs 31

japablo@x86-001:~/spo600/examples/test-clone$ cat clone-test-x86-prune-clone-test-core.c.228t.prune_clones
;; Function scale_samples.resolver (scale_samples.resolver, funcdef_no=27, decl_uid=4477, cgraph_uid=32, symbol_order=30)
[BASE] Found: scale_samples

Running the tests shows when a base function has been found and shows the differences in basic block count between the base and variant!

Reflection

This stage of the project was challenging but rewarding. There was a lot of trial and error along the way. My initial approach to identifying function variants—by checking file extensions, which partially worked.

Resources like the GCC documentation, YouTube tutorials, and StackOverflow were invaluable in helping me discover the right functions to traverse and extract information for fingerprinting.

A big thank you to Professor Chris Tyler as well for providing the test cases, which were conveniently automated using a Makefile.

Conclusion

The hardest part is done! Time to tackle the last part: Prune Suggestion.

SPO600 Project Stage 2, Part 1: “To Prune, or not to Prune”

JP — Sat, 05 Apr 2025 22:41:39 +0000

Introduction

Welcome back! This blog is a continuation from SPO600 Project Stage 1 - where a pass was created that counts the number of basic blocks and GIMPLE statements for a given function.

Project Stage 2 will be the “meat and potatoes” of the project — where variations of a function are compared to determine whether they can be "pruned" or not.

Compiling with gcc is not a one-step process. Instead, there are multiple optimization stages between the source code and the final executable. In each stage, the code can translated into a different form or cloned while remaining functionally the same — which raises the question: can these forms be safely “pruned”?

Gameplan

Background

This problem is similar to LeetCode question 100. Same Tree where the tree can be traversed to identify similarities in their tree structure. However, GIMPLE representations differ in a number of ways:

The control flow graphs contain n-ary tree structures rather than binary trees, where each basic block could have multiple statements and each statement containing different number of operands.
Nodes represent a mix of GIMPLE operations (ASSIGN, CALL, COND, etc.).

Luckily, GCC has APIs for traversing and analyzing these structures, to name few:

gimple.h
gimple-iterator.h
gimple-walk.h
gimple-pretty-print.h

Steps

“Pruning” a function can be determined by:

Identifying all function variations created
Compare each function variations via their GIMPLE representations
Suggest to “prune” if the GIMPLE representations are similar
1. Note: to be considered similar:
  1. Both variations have identical control flow graphs
  2. Both variations have identical number of operands
  3. Both variations have identical operands

Conclusion

Stay tuned! Next blog will explore step 1 of the plan: Identifying all function variations created.

SPO600 Project Stage 1: Gimple and Passes

JP — Mon, 10 Mar 2025 04:47:14 +0000

Introduction

In the previous post, a development instance gcc was set up - where we can experiment and contribute our changes. x86 variants are rapidly growing, where each variant is optimized for different architectures, use cases, etc. gcc unfortunately struggles to keep up with increasing number of platform-specific optimizations, leading to an increasing amount of time when selecting the platform to build .

This project aims to automate the platform selection process, widening the range of supported platforms. The first stage of the project involves the introduction of GIMPLE and “passes”. Specifically focussing on counting the number of basic blocks and statements during compilation, providing insight into code structure.

`GIMPLE`

GIMPLE is a intermediate representation used by gcc when compiling. It breaks down the source code into a lower-level where it can be easier to analyze and manipulate - this becomes important in the optimization stages of compilation where transformations occur to improve performance and efficiency.

Passes

Passes are steps in the compiling process where the code is transformed or analyzed to improve performance, or for efficiency.

Setup and Execution

Overview

Implementing a pass requires 4 major steps:

Define the pass in a source file (.cc)
Register the pass in the sequence of transformations found in passes.def
Modify tree-pass.h to associate the header files for helper functions
Update the Makefile to compile and link the pass

Creating the Pass

The pass must be created in the gcc subfolder (i.e. gcc-source/gcc). A quick ls is this directory will reveal the existing passes and transformations in gcc.

japablo@x86-001:~/gccsrc/gcc$ ls
ABOUT-GCC-NLS                   gimple.def                        range-op-float.cc
acinclude.m4                    gimple-expr.cc                    range-op.h
aclocal.m4                      gimple-expr.h                     range-op-mixed.h
ada                             gimple-fold.cc                    range-op-ptr.cc
addresses.h                     gimple-fold.h                     read-md.cc
adjust-alignment.cc             gimple.h                          read-md.h
alias.cc                        gimple-harden-conditionals.cc     README.Portability

Note: these are some of the transformations. Moving back to the main topic of creating the source code in the pass, here is implementation of the pass.

// gcc/tree-japablo.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"
#include "cgraph.h"
#include "gimple-ssa.h"
#include "attribs.h"
#include "pretty-print.h"
#include "tree-inline.h"
#include "intl.h"
#include "function.h"
#include "basic-block.h"

namespace {
    // Pass metadata definition
    const pass_data my_pass_data = {
        GIMPLE_PASS,       // Pass type (GIMPLE-level pass)
        "japablo",         // Name of the pass
        OPTGROUP_NONE,     // No specific option group
        TV_NONE,           // No timevar (profiling category)
        PROP_cfg,          // Requires CFG (Control Flow Graph)
        0,                 // Properties required (None)
        0,                 // Properties destroyed (None)
        0,                 // Todo flags start
        0                  // Todo flags finish
    };

    // Custom GIMPLE pass class
    class pass_japablo : public gimple_opt_pass {
    public:
        // Constructor: initialize the parent class with the pass context
        pass_japablo(gcc::context *ctx) : gimple_opt_pass(my_pass_data, ctx) {}

        // Execute method: called when the pass runs on a function
        unsigned int execute(function *fun) override {

            printf("\nFunction: %s\n", function_name(fun));

            // Count basic blocks and GIMPLE statements
            int bb_count = 0;
            int stmt_count = 0;

            // Iterate through all basic blocks
            basic_block bb;
            FOR_EACH_BB_FN(bb, fun) {
               ++bb_count;
                for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
                    ++stmt_count;  // Count GIMPLE statements
                }
            }

            printf("Basic blocks: %d\n", bb_count);
            printf("GIMPLE statements: %d\n", stmt_count);

            return 0; // Pass execution successful
        }

        bool gate(function * /* fun */) override {
            return true; // Always run this pass
        }
    };
}

// Factory function to instantiate the pass
gimple_opt_pass *make_pass_japablo(gcc::context *ctxt) {
    return new pass_japablo(ctxt);
}

Namespace and Pass Metadata

namespace {
    const pass_data my_pass_data = {
        GIMPLE_PASS,       // Pass type (GIMPLE-level pass)
        "japablo",         // Name of the pass
        OPTGROUP_NONE,     // No specific option group
        TV_NONE,           // No timevar (profiling category)
        PROP_cfg,          // Requires CFG (Control Flow Graph)
        0,                 // Properties required (None)
        0,                 // Properties destroyed (None)
        0,                 // Todo flags start
        0                  // Todo flags finish
    };
}

This groups the pass definition and metadata - configuring the pass, how it should be behave, and how it fits into gcc.

Custom Pass Class `pass_japablo`

    class pass_japablo : public gimple_opt_pass {
    public:
        // Constructor: initialize the parent class with the pass context
        pass_japablo(gcc::context *ctx) : gimple_opt_pass(my_pass_data, ctx) {}

        // Execute method: called when the pass runs on a function
        unsigned int execute(function *fun) override {

            printf("\nFunction: %s\n", function_name(fun));

            // Count basic blocks and GIMPLE statements
            int bb_count = 0;
            int stmt_count = 0;

            // Iterate through all basic blocks
            basic_block bb;
            FOR_EACH_BB_FN(bb, fun) {
               ++bb_count;
                for (gimple_stmt_iterator gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
                    ++stmt_count;  // Count GIMPLE statements
                }
            }

            printf("Basic blocks: %d\n", bb_count);
            printf("GIMPLE statements: %d\n", stmt_count);

            return 0; // Pass execution successful
        }

        bool gate(function * /* fun */) override {
            return true; // Always run this pass
        }
    };
}

The pass inherits from the gimple_opt_pass, a base class defining a GIMPLE pass. The pass is initialized with the metadata defined previously.

execute takes in a function and prints the name of the function with the number of basic blocks using FOR_EACH_BB_FN, a loop macro in gcc that simplifies iterating over each basic block of a function. The inner loop counts the number of GIMPLE statements using GIMBLE specific functions to iterate over GIMPLE statements in its intermediate form.

Factory Function for the Pass

gimple_opt_pass *make_pass_japablo(gcc::context *ctxt) {
    return new pass_japablo(ctxt);
}

A factory function is used to create an instance of the pass class (i.e. pass_japablo) and create objects (e.g. .o).

Registering the Pass

  NEXT_PASS (pass_assumptions);
  NEXT_PASS (pass_tm_init);
  PUSH_INSERT_PASSES_WITHIN (pass_tm_init)
      NEXT_PASS (pass_tm_mark);
      NEXT_PASS (pass_tm_memopt);
      NEXT_PASS (pass_tm_edges);
  POP_INSERT_PASSES ()
  NEXT_PASS (pass_simduid_cleanup);
  NEXT_PASS (pass_vtable_verify);
  NEXT_PASS (pass_lower_vaarg);
  NEXT_PASS (pass_lower_vector);
  NEXT_PASS (pass_lower_complex_O0);
  NEXT_PASS (pass_lower_bitint_O0);
  NEXT_PASS (pass_sancov_O0);
  NEXT_PASS (pass_lower_switch_O0);
  NEXT_PASS (pass_asan_O0);
  NEXT_PASS (pass_tsan_O0);
  NEXT_PASS (pass_sanopt);
  NEXT_PASS (pass_cleanup_eh);
  NEXT_PASS (pass_musttail);
  NEXT_PASS (pass_lower_resx);
  **NEXT_PASS (pass_japablo);**
  NEXT_PASS (pass_nrv);
  NEXT_PASS (pass_gimple_isel);
  NEXT_PASS (pass_harden_conditional_branches);

Where the pass is placed matters. In this case, pass_japablo will count the basic blocks and statements of the functions that were transformed in previous passes.

Semantics is key in this part. I found out the hard way by putting NEXT_PASS (make_pass_japablo); instead of NEXT_PASS (pass_japablo); resulting in this error:

./pass-instances.def: In constructor ‘gcc::pass_manager::pass_manager(gcc::context*)’:
../../gccsrc/gcc/passes.cc:1624:20: error: ‘make_make_jp_pass’ was not declared in this scope; did you mean ‘make_jp_pass’?
 1624 |       PASS ## _1 = make_##PASS (m_ctxt);          \
      |                    ^~~~~
./pass-instances.def:68:3: note: in expansion of macro ‘NEXT_PASS’
   68 |   NEXT_PASS (make_jp_pass, 1);
      |   ^~~~~~~~~

Luckily, the hints PASS ## _1 = make_##PASS (m_ctxt); and ‘make_make_jp_pass’ was not declared in this scope; did you mean ‘make_jp_pass’? led to the fix

led to the fix.

Modifying `tree-pass.h`

extern gimple_opt_pass *make_pass_tracer (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_warn_restrict (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_warn_unused_result (gcc::context *ctxt);
**extern gimple_opt_pass *make_pass_japablo (gcc::context *ctxt);**

Updating the `Makefile`

OBJS = \
...
 tree-inline.o \
        tree-into-ssa.o \
        tree-iterator.o \
        **tree-japablo.o \**
        tree-logical-location.o \

Rebuilding `gcc`

Rebuilding gcc with the new pass will require to cd into the build directory japablo@x86-001:~/gcc-build-001$ and run make clean. According to the Makefile documentation:

# 3. Use "make clean" to remove the previous build.

Running make clean will give us a clean slate, reducing the chance for build conflicts from a previous build.

Results

Here is a sample of what if printed to the console as japablo-pass is executed.

Function: gimple_simplify_373
Basic blocks: 465
GIMPLE statements: 4630

Let’s recompile the code in lab 4, a simple "hello world" program. The pass should print the number of basic blocks and GIMPLE statements in the simple hello world program.

japablo@x86-001:~/l4$ $HOME/gcc-test-001/bin/gcc test.c -o test

Function: main
Basic blocks: 2
GIMPLE statements: 4

japablo@x86-001:~/l4$ ./test
Hello, World!

Dump File

japablo@x86-001:~/l4$ $HOME/gcc-test-001/bin/gcc -fdump-tree-japablo test.c -o test

Function: main
Basic blocks: 2
GIMPLE statements: 4
japablo@x86-001:~/l4$ cat test.c.264t.japablo 

;; Function main (main, funcdef_no=0, decl_uid=3267, cgraph_uid=1, symbol_order=0)

int main ()
{
  int D.3270;
  int _3;

  <bb 2> :
  __builtin_puts (&"Hello, World!"[0]);
  _3 = 0;

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

}

Conclusion

This stage of the project will serve as the basis on how to analyze the intermediate representation of source code. Being exposed to the underlying transformations of gcc made me realize how complex a “hello world” program is. There are hundreds of optimizations happening “under the hood”, none that I am familiar with but made me curious to look into the source code of one of the “simpler” transformations and possibly experiment with it.

So far I have been mostly studying and working with high-level programming and concepts and never had the opportunity to work with lower level code. Low-level programming is verbose and requires a deeper understanding of memory management, CPU architecture, etc. Excited to continue onto the next stage - let the experimenting begin!

SPO600 Lab 5 - Analyzing and Experimenting with Assembly

JP — Wed, 05 Mar 2025 15:59:04 +0000

Introduction

x86 and aarch64 have a more rich set of instructions compared to 6502 - the former is far more capable with complex operations. Each architecture are designed with different goals - x86 prioritizes raw performance, aarch64 prioritizes power efficiency, and 6502 is simple and cost efficient (relative to today’s standards).

Let’s slowly get introduced to the x86 and aarch64 instruction set by analyzing a simple “Hello World” program, then experiment with loops.

Preparing the Lab Environment

The source code was obtained by using tar:

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

This will extract the contents into the current directory - I decided to extract it into my labs/l5 directory.

The source code directory follows this structure (Source):

 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`

Navigate to the spo600/examples/hello/assembler/aarch64 and run make, the will assemble and link to create an executable named hello.

Comparing the source code hello.s to the disassembled output by using objdump -d hello.o.

[japablo@aarch64-002 aarch64]$ cat 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
[japablo@aarch64-002 aarch64]$ objdump -d 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

The dissembled output is the machine readable version of the source code. Both versions have 8 instructions and each line starts with where the instruction starts followed by the binary code being executed followed by the corresponding human-readable instruction.

Loops

The first step is to produce a loop to print “Loop” 5 times.

The high level instructions are as follows:

create a string variable Loop:
have a min and max value, defines the number of loops
initiate a variable to track loop iteration
print the string variable Loop:
print newline
increment the loop counter
check if iteration reaches the max value

    .section .data
msg:    .ascii "Loop: "        // message prefix (6 bytes)
digit:  .byte '0'              // placeholder for the loop index (initialized to '0')
newline:.ascii "\n"            // newline character (1 byte)

    .section .text
    .globl _start

    min = 0                    
    max = 6                    

_start:
    mov     x19, min           // init loop counter (x19 = 0)

loop:
    // Write "Loop: "
    mov     x0, 1              // file descriptor: stdout (1)
    ldr     x1, =msg           // load address of "Loop: "
    mov     x2, 6              // length: 6 bytes ("Loop: ")
    mov     x8, 64             // syscall: write (64)
    svc     0                  // invoke syscall

    // Print newline character
    mov     x0, 1             
    ldr     x1, =newline       // load address of newline character
    mov     x2, 1              // length: 1 byte
    mov     x8, 64             // syscall: write (64)
    svc     0                  // invoke syscall

    // Increment loop counter and check condition
    **add     x19, x19, 1**        // x19 = x19 + 1
    cmp     x19, max           // compare x19 to max (6)
    b.ne    loop               // if not equal, continue loop

    // Exit program
    mov     x0, 0              // exit status: 0
    mov     x8, 93             // syscall: exit (93)
    svc     0                  // invoke syscall

Loop:
Loop:
Loop:
Loop:
Loop:
Loop:

The instructions function similar to 6502 where values are loaded in and out of registers, and these values can be compared by references an address. The add instruction is not found in 6502 but exists in aarch64, where it sums 2 operands and stores it in an address. Performing addition in 6502 is verbose, requiring to track the carry flag, and loading values in and out of memory and the accumulator.

Loop with Iteration Number

Next is to print the iteration next to Loop: (e.g. Loop: 1). The bolded instructions is what was added to include the iteration number in each loop.

    .section .data
msg:    .ascii "Loop: "        
**digit:  .byte '0'**              // placeholder for the loop index (initialized to '0')
newline:.ascii "\n"            // newline character (1 byte)

    .section .text
    .globl _start

    min = 0                    // loop start index
    max = 6                    // loop exit condition (exclusive)

_start:
    mov     x19, min            // initialize loop counter (x19 = 0)

loop:
    // Write "Loop: "
    mov     x0, 1              // file descriptor: stdout (1)
    ldr     x1, =msg           // load address of "Loop: "
    mov     x2, 6              // length: 6 bytes ("Loop: ")
    mov     x8, 64             // syscall: write (64)
    svc     0                  // invoke syscall

    **// Convert loop index to ASCII and print it
    mov     x0, 1              
    ldr     x1, =digit         // load address of digit buffer
    add     w20, w19, '0'      // convert loop index to ASCII (0x30)
    strb    w20, [x1]          // store ASCII character in buffer
    mov     x2, 1              // length: 1 byte (single digit)
    mov     x8, 64             // syscall: write (64)
    svc     0                  // invoke syscall**

    // Print newline character
    mov     x0, 1              
    ldr     x1, =newline       // load address of newline character
    mov     x2, 1              // length: 1 byte
    mov     x8, 64             // syscall: write (64)
    svc     0                  // invoke syscall

    // Increment loop counter and check condition
    add     x19, x19, 1        // x19 = x19 + 1
    cmp     x19, max           // compare x19 to max (6)
    b.ne    loop               // if not equal, continue loop

    // Exit program
    mov     x0, 0              // exit status: 0 (success)
    mov     x8, 93             // syscall: exit (93)
    svc     0                  // Invoke syscall

Loop: 0
Loop: 1
Loop: 2
Loop: 3
Loop: 4
Loop: 5

add converts the current iteration (in w19) into its respective ASCII value to be printed in the console. It does this by adding the numerical value to 0x30 (adding to 0x30 acts as an offset when converting to ASCII) then storing the ASCII value in register w20. digit is updated with the the value in w20 with strb w20, [x1].

Loop to 32

    .section .data
msg:    .ascii "Loop: "          
digits: .ascii "00"             // Buffer to hold 2-digit number
newline:.ascii "\n"             

    .section .text
    .globl _start

    min = 0                      
    max = 33                     

_start:
    mov     x19, min             

loop:
    // Write "Loop: "
    mov     x0, 1                // file descriptor: stdout (1)
    ldr     x1, =msg             // load address of "Loop: "
    mov     x2, 6                // length: 6 bytes
    mov     x8, 64               // syscall: write (64)
    svc     0                    // invoke syscall

    **// Convert x19 to 2-digit ASCII
    mov     x20, x19             // copy loop counter

    // Divide by 10 to extract the tens digit
    mov     x21, 10
    udiv    x22, x20, x21        // x22 = quotient (tens place)
    msub    x23, x22, x21, x20   // x23 = remainder (ones place)

    add     w22, w22, '0'        // convert quotient to ASCII
    add     w23, w23, '0'        // convert remainder to ASCII

    ldr     x1, =digits          // load address of digits buffer
    strb    w22, [x1]            // store tens digit
    strb    w23, [x1, 1]         // store ones digit

    // Write the 2-digit number
    mov     x0, 1                
    mov     x2, 2                // length: 2 bytes
    mov     x8, 64               // syscall: write (64)
    svc     0                    // invoke syscall

    // Write newline character
    mov     x0, 1                
    ldr     x1, =newline         // load address of newline character
    mov     x2, 1                // length: 1 byte
    mov     x8, 64               // syscall: write (64)
    svc     0                    // invoke syscall**

    // Increment loop counter and check condition
    add     x19, x19, 1          // x19 = x19 + 1
    cmp     x19, max             // compare x19 to max (33)
    b.ne    loop                 // if not equal, continue loop

    // Exit program
    mov     x0, 0                // exit status: 0 (success)
    mov     x8, 93               // syscall: exit (93)
    svc     0                    // invoke syscall

Loop: 00
Loop: 01
Loop: 02
Loop: 03
Loop: 04
Loop: 05
Loop: 06
Loop: 07
Loop: 08
Loop: 09
Loop: 10
Loop: 11
Loop: 12
Loop: 13
Loop: 14
Loop: 15
Loop: 16
Loop: 17
Loop: 18
Loop: 19
Loop: 20
Loop: 21
Loop: 22
Loop: 23
Loop: 24
Loop: 25
Loop: 26
Loop: 27
Loop: 28
Loop: 29
Loop: 30
Loop: 31
Loop: 32

The addition of udiv and msub calculates the tens and ones digits, respectively.

udiv, unsigned division, takes our loop counter stored in x20, and 10 stored in x21, and stores the quotient (tens digit) in x22.

In the first iteration, when x20 (the loop counter) is 0, the operation:

udiv x22, x20, x21

Calculates:

x22 = 0 ÷ 10 → 0 (tens digit)

Since the quotient is 0, the tens digit remains 0.

Next, the msub instruction is used to calculate the remainder (ones digit):

msub x23, x22, x21, x20

This performs the following calculation:

x23 = x20 - (x22 * x21)
    = 0 - (0 * 10)
    = 0 (ones digit)

So, for the first iteration (x20 = 0), both x22 (tens) and x23 (ones) are 0.

Loop to 32 Without Trailing 0’s

    .section .data
msg:    .ascii "Loop: "          
digits: .ascii "00"             // buffer to hold 2-digit number
newline:.ascii "\n"             

    .section .text
    .globl _start

    min = 0                      
    max = 33                     

_start:
    mov     x19, min             // initialize loop counter (x19 = 0)

loop:
    // Write "Loop: "
    mov     x0, 1                // file descriptor: stdout (1)
    ldr     x1, =msg             // load address of "Loop: "
    mov     x2, 6                // length: 6 bytes
    mov     x8, 64               // syscall: write (64)
    svc     0                    // invoke syscall

    // Convert x19 to 2-digit ASCII
    mov     x20, x19             // copy loop counter

    // Divide by 10 to extract the tens digit
    mov     x21, 10
    udiv    x22, x20, x21        // x22 = quotient (tens place)
    msub    x23, x22, x21, x20   // x23 = remainder (ones place)

    add     w22, w22, '0'        // convert quotient to ASCII
    add     w23, w23, '0'        // convert remainder to ASCII

    **ldr     x1, =digits          // load address of digits buffer

    // Handle leading zeros
    cmp     x19, 10              // check if the number is less than 10
    blt     print_ones_only      

    // Store both digits
    strb    w22, [x1]            // store tens digit
    strb    w23, [x1, 1]         // store ones digit

    mov     x0, 1                // file descriptor: stdout (1)
    mov     x2, 2                // length: 2 bytes
    b       write_digits

print_ones_only:
    mov     w22, ' '             // clear the tens place with a space
    strb    w22, [x1]            // store space in the tens place
    strb    w23, [x1, 1]         // store ones digit
    mov     x0, 1                // file descriptor: stdout (1)
    mov     x2, 2                // length: 2 bytes**

write_digits:
    mov     x8, 64               // syscall: write (64)
    svc     0                    // invoke syscall

    // Write newline character
    mov     x0, 1                
    ldr     x1, =newline         // load address of newline character
    mov     x2, 1                // length: 1 byte
    mov     x8, 64               // syscall: write (64)
    svc     0                    // invoke syscall

    // Increment loop counter and check condition
    add     x19, x19, 1          // x19 = x19 + 1
    cmp     x19, max             // compare x19 to max (33)
    b.ne    loop                 // if not equal, continue loop

    // Exit program
    mov     x0, 0                // exit status: 0 (success)
    mov     x8, 93               // syscall: exit (93)
    svc     0                    // invoke syscall

Loop:  0
Loop:  1
Loop:  2
Loop:  3
Loop:  4
Loop:  5
Loop:  6
Loop:  7
Loop:  8
Loop:  9
Loop: 10
Loop: 11
Loop: 12
Loop: 13
Loop: 14
Loop: 15
Loop: 16
Loop: 17
Loop: 18
Loop: 19
Loop: 20
Loop: 21
Loop: 22
Loop: 23
Loop: 24
Loop: 25
Loop: 26
Loop: 27
Loop: 28
Loop: 29
Loop: 30
Loop: 31
Loop: 32

If the iteration is greater or equal to 10, the loop is the same otherwise, it will branch to print_ones_only via blt, where it will clear out the memory storing the tens values, then load the empty tens value followed by the ones value into digit.

Looping to 32 with Hex Values

    .section .data
msg:    .ascii "Loop: "          
digits: .ascii "00"             
newline:.ascii "\n"             

    .section .text
    .globl _start

    min = 0                      
    max = 33                     

_start:
    mov     x19, min              

loop:
    // Write "Loop: "
    mov     x0, 1                // file descriptor: stdout (1)
    ldr     x1, =msg             // load address of "Loop: "
    mov     x2, 6                // length: 6 bytes
    mov     x8, 64               // syscall: write (64)
    svc     0                    // invoke syscall

    // Convert x19 to 2-digit hexadecimal
    mov     x20, x19             // copy loop counter

    // Get the hexadecimal value
    mov     x21, 16              // hexadecimal base (16)
    udiv    x22, x20, x21        // x22 = quotient (tens place)
    msub    x23, x22, x21, x20   // x23 = remainder (ones place)

    **// Convert quotient and remainder to ASCII (hex digits)
    add     w22, w22, '0'        // convert quotient to ASCII (0-9 or A-F)
    add     w23, w23, '0'        // convert remainder to ASCII (0-9 or A-F)
    cmp     w22, '9'             // check if quotient is greater than 9 (A-F)
    ble     no_hex_conversion    // if less than or equal to '9', skip
    add     w22, w22, 7          // convert 'A' - 'F' (10-15)
no_hex_conversion:
    cmp     w23, '9'             // check if remainder is greater than 9 (A-F)
    ble     no_hex_conversion_2  // if less than or equal to '9', skip
    add     w23, w23, 7          // convert 'A' - 'F' (10-15)

no_hex_conversion_2:
    ldr     x1, =digits          // load address of digits buffer

    // Store both digits
    strb    w22, [x1]            // store quotient (tens place)
    strb    w23, [x1, 1]         // store remainder (ones place)

    mov     x0, 1                // file descriptor: stdout (1)
    mov     x2, 2                // length: 2 bytes**
    b       write_digits

print_ones_only:
    mov     w22, ' '             // clear the tens place with a space
    strb    w22, [x1]            // store space in the tens place
    strb    w23, [x1, 1]         // store ones digit
    mov     x0, 1                // file descriptor: stdout (1)
    mov     x2, 2                // length: 2 bytes

write_digits:
    mov     x8, 64               // syscall: write (64)
    svc     0                    // invoke syscall

    // Write newline character
    mov     x0, 1                
    ldr     x1, =newline         // load address of newline character
    mov     x2, 1                // length: 1 byte
    mov     x8, 64               // syscall: write (64)
    svc     0                    // invoke syscall

    // Increment loop counter and check condition
    add     x19, x19, 1          // x19 = x19 + 1
    cmp     x19, max             
    b.ne    loop                 // if not equal, continue loop

    // Exit program
    mov     x0, 0                // exit status: 0 (success)
    mov     x8, 93               // syscall: exit (93)
    svc     0                    // invoke syscall

The usual conversion to ASCII determines whether or not the tens and or ones need to offset to display its hexadecimal equivalent. Specially, cmp w22, '9' and ble no_hex_conversion check if the tens is below 9, branching to no_hex_conversion where it checks if the ones need conversion.

The conversion to hexadecimal is adding an offset of 7 to its correspondent numerical value - resulting in a value between A-F.

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`

The same approach was taken with x86 for each loop, Link to GitHub containing both x86 and aarch64 implementations.

Results

The history of each architecture plays a role on how the data is handled. x86 was first introduced in 1978 with the Intel 8086 as a 16-bit processor (Source). x86-64 is also backwards compatible, meaning that 64 bit processor should work on 32 bit programs but not 16 bit programs directly. aarch64 is relatively new, first introduced in 2011 as part of the ARMv8 architecture (Source). As we have seen, it uses RISC (Reduced Instruction Set Computer) design with a fixed 32-bit instruction size. While x86-64 prioritizes backward compatibility, aarch64 maintains a cleaner instruction set and may support 32-bit ARM code on some hardware, though newer devices are 64-bit only.

These design differences can be seen in how the iteration number is converted into its hexadecimal value.

Extracting Tens and Ones

In x86, it handles the data in nibbles (4 bits), where it holds the tens and ones. The instruction shr rax, 4 shifts the value right by 4 bits to isolate the high nibble (tens place) in the lower 4 bits of the register. The instruction and al, 0x0F performs a bitwise AND operation to isolate the low nibble (ones place) by masking out the upper 4 bits.

In aarch64, the values are handled using arithmetic operations like udiv (for division) and msub (for remainder), which extract the tens and ones values directly. In contrast, x86 uses bitwise operations such as shr (shift right) and and (masking) to extract the tens and ones values by manipulating individual bits and nibbles.

Conclusion

Each architecture produces the same result for each loop but their approaches differ. The history and design choices of each architecture partly explain why. aarch64 simplifies the complex operations of multiplication and division whereas x86 is quite verbose. The level of verbosity in x86 however does boost its performance because of direct management of bits with bitwise manipulation, and shifting - allowing for optimizations where possible.

SPO600 Lab 4 - x86 GCC vs aarch64 GCC

JP — Mon, 03 Mar 2025 16:36:44 +0000

Introduction

Processors can differ in their design (i.e. architecture) to satisfy different requirements. One of the most oldest and well known architectures is x86, introduced in 1978 by Intel, is optimized for performance in desktops and servers with the cost of high power consumption (Source, Source 2).

In 2020, Apple released their first in-house processor the M-Series processors (Source). The processor is based off the aarch64 architecture with the goal of being more energy efficient compared to x86.

Each architecture has their own unique set of instructions. Therefore instructions for x86 won’t work on aarch64 and vice versa. When programming either low level (e.g. C, C++), or high level languages (e.g. Python, JavaScript) both need to go through a compiler - where the source code is translated into machine code specific to the architecture it is being compiled on.

Here’s a table of popular programming languages with their associated compiler:

Programming Language	Compiler
C	GCC, Clang
C++	G++, Clang++
Python	CPython, PyPy
JavaScript	V8

`GCC`

GCC is an open-source C compiler, part of the GNU Compiler Collection. An advantage of GCC is its extensive portability, as it can be compiled for a wide range of popular, and emerging architectures. List of supported architectures.

Lab 4

GCC can be ported and used on x86 and aarch64 architectures. Having access to both architectures, the GCC source code can be cloned via GitHub and installed locally.

Predictions

Given the differences between the x86 and aarch64 architectures, I predict that x86 will compile GCC quicker than aarch64.

Possible Issues

A factor that contributes to a quicker compile time is the amount of RAM, the x86 system has 64GB of RAM whereas the aarch64 system only has 32GB - this issue can limit how much physical RAM can be utilized and force memory swaps (i.e. moving data between RAM and the hard drive).

The servers being used to compile GCC are also shared. Therefore, depending when compiling occurs, the resources can be limited and also effect the compile times.

Setup

The setup will be the same between systems. It’s possible to have multiple instances of GCC on a single machine - to differentiate each GCC build, a dedicated directory is created and a subdirectory is dedicated for the source code and another for the build. After building GCC we could specify which gcc to use to compile a C program.

The following steps will guide you on how to get the GCC source code to building and compiling a C program using the newly installed GCC:

Create and cd into the source code directory
```
mkdir -p ~/gcc-dev && cd ~/gcc-dev
```

Clone the GCC source code

git clone https://gcc.gnu.org/git/gcc.git

Create and cd into the build folder, this is where the GCC build will happen
```
cd ..
mkdir build-gcc
cd build-gcc
```

Get the requirements needed to compile GCC for the system architecture

../gcc/configure --prefix=$HOME/gcc-build-x86-001/install --enable-languages=c,c++ --disable-multilib

Build GCC via the Makefile and use time to log the runtime into build.log
```
time make -j$(nproc) 2>&1 | tee build.log
```

Verify `GCC` Compilation

We’ll check the version of the installed GCC compiler and compile test.c that prints out “Hello World” to the console.

#include <stdio.h>

int main() {
    printf("Hello, World!\n");
    return 0;
}

aarch64

[japablo@aarch64-002 l4]$ $HOME/gcc-build-x86-001/install/bin/gcc --version
gcc (GCC) 15.0.1 20250224 (experimental)
Copyright (C) 2025 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

[japablo@aarch64-002 l4]$ $HOME/gcc-build-x86-001/install/bin/gcc test.c -o test
[japablo@aarch64-002 l4]$ ./test
Hello, World!

x86

japablo@x86-001:~/gcc-dev/build-gcc$ $HOME/gcc-build-x86-001/install/bin/gcc --version
gcc (GCC) 15.0.1 20250224 (experimental)
Copyright (C) 2025 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

japablo@x86-001:~/l4$ $HOME/gcc-build-x86-001/install/bin/gcc test.c -o test
japablo@x86-001:~/l4$ ./test
Hello, World!

Results

It was hypothesized that the x86 system would finish quicker than aarch64 because of faster clock speeds.

# x86 
**real  34m44.825s**
user    385m35.938s
sys 13m4.008s

# aarch64
**real  107m55.004s**
user    998m11.630s
sys 31m39.209s

For aarch64 system, it is said to compile gcc in approximately 100 min according to the system description here. The resulting aarch64 did take approximately 7 minutes longer than expected.

Lab 3 - Wrapping up 6502 Assembly

JP — Mon, 10 Feb 2025 20:28:01 +0000

Introduction

Welcome back! We’ll be concluding the 6502 series by creating a program that covers 3 main topics:

Character output
Character input
A form of arithmetic (e.g. add, subtract, bitwise operations, etc.)

I decided to create a “simple” addition calculator. I quote “simple” because adding is on pencil and paper, and in most programming languages goes something like this:

1 + 1 = 2

When performing addition on paper, we add the ones, carry the ten (if any), add the tens, etc. Luckily 6502 assembly follows a similar process but with added complexity of memory and bit management. I’ll explain how the addition works along the way. Let’s jump straight into the program!

Addition Calculator

Overview

Here’s the entirety of the code, feel free to use it in the 6502 emulator. Don’t worry, I’ll explain how it works in the following sections!

Note: the character in and out sections of the code were taken from SPO600 week 4 class demonstration and can be found here.

; Predefined ROM Routines, found in their respective addresses
define SCINIT  $ff81 
define CHRIN   $ffcf
define CHROUT  $ffd2
define SCREEN  $ffed
define PLOT    $fff0

; Zero page memory locations
define INPUT1  $0010
define INPUT2  $0011
define RESULT  $0012

; ASCII Character constants
define BACKSPACE $08  
define ENTER     $0D  
define SPACE     $20
define BLACK     $A0
define LEFT      $83

; CODE TO TEST INPUT
START:
    JSR SCINIT  ; Initialize screen
    LDY #$00    ; Index for first number
    LDX #$00    ; Index for second number

; Display the initial message only once
LOOPFIRST:
    LDA PROMPTFIRST,Y
    BEQ GETFIRST
    JSR CHROUT 
    INY
    JMP LOOPFIRST

GETFIRST:
    JSR INPUTFIRST  ; Get first digit
    LDY #$00

LOOPSECOND:
    LDA PROMPTSECOND,Y
    BEQ GETSECOND
    JSR CHROUT
    INY
    JMP LOOPSECOND

GETSECOND:
    JSR INPUTSECOND  ; Get second digit
    LDY #$00

; Convert ASCII to number and add
    LDA INPUT1
    SEC
    SBC #$30   ; Convert ASCII to numerical value
    STA INPUT1 ; Store numerical value

    LDA INPUT2
    SEC
    SBC #$30   ; Convert ASCII to numerical value
    STA INPUT2 ; Store numerical value

    CLC        ; Clear carry flag before addition
    LDA INPUT1
    ADC INPUT2 ; Add the two numbers
    STA RESULT ; Store result

    LDY #$00

LOOPCONFIRM:
    LDA CONFIRM,Y
    BEQ PRINT_RESULT
    JSR CHROUT 
    INY
    JMP LOOPCONFIRM

PRINT_RESULT:
    LDA RESULT        ; Load the result
    CMP #10           ; Check if the result is greater than or equal to 10
    BPL TWO_DIGITS    ; If yes -> handle two digits

    ; Single-digit result
    CLC               ; Clear carry flag before ASCII conversion
    ADC #$30          ; Convert to ASCII
    JSR CHROUT        ; Display the result
    JMP END_PROGRAM

; Handle two-digit result
TWO_DIGITS:
    SEC
    SBC #10           ; Subtract 10 to get the units digit
    PHA               ; Save the units digit
    LDA #$31          ; Load ASCII for '1' (tens digit)
    JSR CHROUT        ; Display the tens digit
    PLA               ; Restore the units digit
    CLC               ; Clear carry flag before ASCII conversion
    ADC #$30          ; Convert to ASCII
    JSR CHROUT        ; Display the units digit

END_PROGRAM:
    BRK  ; End program

; PROMPTS
PROMPTFIRST:
    dcb "S", "P", "O", "6", "0", "0", 32, "L", "a", "b", 32, "3", 32, "-", 32, "A", "d", "d", 32, "2", 32, "N", "u", "m", "b", "e", "r", "s", $0D
    dcb "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", $0D
    dcb "E", "N", "T", "E", "R", 32, "F", "I", "R", "S", "T", 32, "D", "I", "G", "I", "T", 32, "(", "0", "-", "9", ")", ":", 32, $00

PROMPTSECOND:
    dcb $0D, "E", "N", "T", "E", "R", 32, "S", "E", "C", "O", "N", "D", 32, "D", "I", "G", "I", "T", 32, "(", "0", "-", "9", ")", ":", 32, $00

CONFIRM:
    dcb $0D, $0D, "S", "U", "M", ":", 32, $00

; Subroutine to input first number
INPUTFIRST:
    LDY #$00    

GETKEY1: 
    LDA #BLACK           ; Black cursor color
    JSR CHROUT           
    LDA #LEFT            
    JSR CHROUT           

    JSR CHRIN            ; Get character from input
    CMP #$00             ; Check if key pressed
    BEQ GETKEY1          

    CMP #BACKSPACE       ; Check for backspace
    BNE CHECKENTER1      ; If not backspace, proceed

    ; Handle backspace
    CPY #$00             ; If nothing to delete, ignore
    BEQ GETKEY1
    DEY                  ; Move the cursor back by one
    LDA #SPACE           ; Clear the previous character using the SPACE character
    JSR CHROUT           ; Display the space to erase the character
    LDA #LEFT            ; Move cursor back one space
    JSR CHROUT           ; Apply cursor move
    JSR CHROUT           ; Redraw the cursor

    JMP GETKEY1

CHECKENTER1:
    CMP #ENTER
    BEQ CHECKCOUNT1

CHECKLETTER1:
    CMP #$30             ; Check if character is less than '0'
    BMI GETKEY1          ; If less, reject it
    CMP #$3A             ; Check if character is greater than '9' ($39 + 1)
    BPL GETKEY1          ; If greater, reject it

    CPY #$01             ; Check if we already have one digit
    BEQ GETKEY1          ; If yes, reject additional input

    STA INPUT1,Y         ; Store the valid digit
    JSR CHROUT           ; Display the character
    INY
    JMP GETKEY1

CHECKCOUNT1:
    CPY #1               ; Check if we have exactly one digit
    BNE GETKEY1          ; If not, continue waiting
    RTS  

; Subroutine to input second number 
INPUTSECOND:
    LDY #$00  

GETKEY2: 
    LDA #BLACK          
    JSR CHROUT          
    LDA #LEFT            
    JSR CHROUT          

    JSR CHRIN            ; Get character from input
    CMP #$00             ; Check if key pressed
    BEQ GETKEY2          ; If no key pressed, continue waiting

    CMP #BACKSPACE       ; Check for backspace
    BNE CHECKENTER2      ; If not backspace, proceed

    ; Handle backspace
    CPY #$00             ; If nothing to delete, ignore
    BEQ GETKEY2
    DEY                  ; Move the cursor back by one
    LDA #SPACE           ; Clear the previous character using the SPACE character
    JSR CHROUT           ; Display the space to erase the character
    LDA #LEFT            ; Move cursor back one space
    JSR CHROUT           ; Apply cursor move
    JSR CHROUT           ; Redraw the cursor

    JMP GETKEY2   

CHECKENTER2:
    CMP #ENTER
    BEQ CHECKCOUNT2   

CHECKLETTER2:
    CMP #$30             ; Check if character is less than '0'
    BMI GETKEY2          ; If less, reject it
    CMP #$3A             ; Check if character is greater than '9' ($39 + 1)
    BPL GETKEY2          ; If greater, reject it

    CPY #$01             ; Check if we already have one digit
    BEQ GETKEY2          ; If yes, reject additional input

    STA INPUT2,Y         ; Store the valid digit
    JSR CHROUT           ; Display the character
    INY
    JMP GETKEY2

CHECKCOUNT2:
    CPY #1               ; Check if we have exactly one digit
    BNE GETKEY2          ; If not, continue waiting
    RTS

Macros

Let’s start with understanding the macros in the program, those with the define keyword.

; Predefined ROM Routines, found in their respective addresses
define SCINIT  $ff81 
define CHRIN   $ffcf
define CHROUT  $ffd2
define SCREEN  $ffed
define PLOT    $fff0

; Zero page variables
define INPUT1  $0010
define INPUT2  $0011
define RESULT  $0012

; ASCII Character constants
define BACKSPACE $08  
define ENTER     $0D  
define SPACE     $20
define BLACK     $A0
define LEFT      $83

ROM Routines

ROM routines are predefined routines that can be accessed by their respective addresses. It is similar to the standard libraries in C/C++ where functions are written to handle tedious processes.

Let’s quickly go through each ROM routine, listed here:

SCINIT — initialize screen, clearing data in the bitmap display
CHRIN — character in, input keyboard characters
CHROUT — output character to the screen
PLOT — get/set cursor coordinates

Zero Page Variables

Zero page variables are special because they are located in the first 256 bytes of memory ($0000 - $00FF) and therefore have faster access times relative to non-zero page variables. INPUT1, INPUT2, and RESULT will hold the first number, second number, and sum respectively.

ASCII Characters

Characters are read in their hexadecimal representation. To read user input, the value can be compared to one of the ASCII characters and the appropriate action can be executed (e.g. BACKSPACE removes a character from the screen). In the code, each key is encoded as their respective hexadecimal value.

Reference of ASCII characters: Link

User Input

There are a couple of key checks in the user input:

Check if input ranges from 0-9
Handling the ENTER key
Handling the BACKSPACE key

; Subroutine to input first number
INPUTFIRST:
    LDY #$00    

GETKEY1: 
    LDA #BLACK           ; Black cursor color
    JSR CHROUT           
    LDA #LEFT            
    JSR CHROUT           

    JSR CHRIN            ; Get character from input
    CMP #$00             ; Check if key pressed
    BEQ GETKEY1          

    CMP #BACKSPACE       ; Check for backspace
    BNE CHECKENTER1      ; If not backspace, proceed

    ; Handle backspace
    CPY #$00             ; If nothing to delete, ignore
    BEQ GETKEY1
    DEY                  ; Move the cursor back by one
    LDA #SPACE           ; Clear the previous character using the SPACE character
    JSR CHROUT           ; Display the space to erase the character
    LDA #LEFT            ; Move cursor back one space
    JSR CHROUT           ; Apply cursor move
    JSR CHROUT           ; Redraw the cursor

    JMP GETKEY1

CHECKENTER1:
    CMP #ENTER
    BEQ CHECKCOUNT1

CHECKLETTER1:
    CMP #$30             ; Check if character is less than '0'
    BMI GETKEY1          ; If less, reject it
    CMP #$3A             ; Check if character is greater than '9' ($39 + 1)
    BPL GETKEY1          ; If greater, reject it

    CPY #$01             ; Check if we already have one digit
    BEQ GETKEY1          ; If yes, reject additional input

    STA INPUT1,Y         ; Store the valid digit
    JSR CHROUT           ; Display the character
    INY
    JMP GETKEY1

CHECKCOUNT1:
    CPY #1               ; Check if we have exactly one digit
    BNE GETKEY1          ; If not, continue waiting
    RTS

The Y register acts as an index in order to access the characters in the PROMPT instructions, as well as keeping track of input length.

Note: the input is being compared in their respective hexadecimal values.

`GETKEY`

GETKEY validates the input in the accumulator. First it prints out the black cursor, then waits until a character is inputted. If the input is a backspace, then it checks if the Y register is 0, if it’s 0 then it means that there is nothing to delete and loops back to itself. Otherwise it will decrement Y and replace the character with a space to clear out the character in the display.

`CHECKENTER`

CHECKENTER checks if user presses the ENTER key, and directs the program to CHECKCOUNT where it checks if there is a character.

`CHECKCOUNT`

CHECKCOUNT checks if there is exactly 1 character, this is needed because when pressing enter, it is not guaranteed there is any inpu*t. This means that we are limited to single digits for the numbers being added.* If input is empty, the program returns to GETKEY waiting until the user inputs a character.

`CHECKLETTER`

CHECKLETTER is the final step in input validation, at this point, we can assume that the input is non-empty. Next is to validate that it is a character ranging from 0-9.

The same process is repeated for getting the second number.

Performing Addition

Converting ASCII to Numerical Value

At this point, the inputted values have been represented as ASCII values. However the ASCII value of a number is not equal to its numerical value. For example, the number 1 is equal to 31 in hexadecimal, 2 is equal to 32, etc. Therefore, there is an offset of 30.

To convert the ASCII into it’s proper numerical value, 30 will needs to be subtracted from its ASCII value.

GETSECOND:
    JSR INPUTSECOND  ; Get second digit
    LDY #$00

; Convert ASCII to number and add
    LDA INPUT1
    SEC
    SBC #$30   ; Convert ASCII to numerical value
    STA INPUT1 ; Store numerical value

    LDA INPUT2
    SEC
    SBC #$30   ; Convert ASCII to numerical value
    STA INPUT2 ; Store numerical value

    CLC        ; Clear carry flag before addition
    LDA INPUT1
    ADC INPUT2 ; Add the two numbers
    STA RESULT ; Store result

    LDY #$00

Once converted, the value is stored into it’s respective zero page variable defined previously.

Performing Addition

    CLC        ; Clear carry flag before addition
    LDA INPUT1
    ADC INPUT2 ; Add the two numbers
    STA RESULT ; Store result

The carry flag may be set from previous operations, and needs to be cleared before addition occurs. Once cleared, INPUT1 is loaded into the accumulator and ADC INPUT2 adds INPUT2 to INPUT1 and the carry flag will be set if the result exceeds 255. The result is then stored into the RESULT memory address from the accumulator.

Printing the Result

At this point, the result is stored in its numerical representation. However when displaying with CHROUT, the result needs to be in its ASCII representation. For example, if the result was 9, without converting to its ASCII, it would display a horizontal tab.

CHROUT prints the character in the accumulator and must be in it’s ASCII representation. Since ASCII is limited to single digits e.g. there is no ASCII for 10, 11, 123, etc.) each number has be printed individually (e.g. printing the tens, ones, etc.).

PRINT_RESULT:
    LDA RESULT        ; Load the result
    CMP #10           ; Check if the result is greater than or equal to 10
    BPL TWO_DIGITS    ; If yes -> handle two digits

    ; Single-digit result
    CLC               ; Clear carry flag before ASCII conversion
    ADC #$30          ; Convert to ASCII
    JSR CHROUT        ; Display the result
    JMP END_PROGRAM

; Handle two-digit result
TWO_DIGITS:
    SEC
    SBC #10           ; Subtract 10 to get the units digit
    PHA               ; Save the units digit
    LDA #$31          ; Load ASCII for '1' (tens digit)
    JSR CHROUT        ; Display the tens digit
    PLA               ; Restore the units digit
    CLC               ; Clear carry flag before ASCII conversion
    ADC #$30          ; Convert to ASCII
    JSR CHROUT        ; Display the units digit

In PRINT_RESULT, if RESULT is greater than 9, then we need to handle the printing where the tens is printed first followed by the ones. Otherwise, 30 is added to the sum to convert it into its ASCII form.

Printing 2 Digit Sum

In the case of a 2 digit sum, TWO_DIGITS the carry flag is set SEC in order to carry out subtraction SBC. The result is then subtracted by 10 then the difference is pushed onto the stack PHA - this represents the number in the “ones” column.

; Handle two-digit result
TWO_DIGITS:
    SEC
    SBC #10           ; Subtract 10 to get the units digit
    PHA               ; Save the units digit
    LDA #$31          ; Load ASCII for '1' (tens digit)
    JSR CHROUT        ; Display the tens digit
    PLA               ; Restore the units digit
    CLC               ; Clear carry flag before ASCII conversion
    ADC #$30          ; Convert to ASCII
    JSR CHROUT        ; Display the units digit

The ASCII value for 1 is then printed, note that the max sum is 18, therefore, 1 is the largest value in the tens column. The “ones” column value is restored into the accumulator via PLA and then printed. Using the stack was inspired by user “barrym95838” from the 6502 forum (Link).

Conclusion

The open ended nature of this lab - where I choose what program to create was both a blessing and a curse. I was confident in managing the bits using the LDA, STA, etc. methods, with both immediate and absolute addressing modes - used to get and set the values.

Where I had the most issue is dealing with outputting the 2 digit results. My first attempt resulted in the “ones” column being printed (i.e. without the “tens” column). For example 9 + 9 would print out 8 , the second digit of the sum of 18. Researching online has led to an interesting solution previously mentioned with the use of the stack.

Overall I am happy with the program and excited to start with 64-bit compilers.

SPO600 Lab 2 - Animating on the Bitmap Display

JP — Mon, 03 Feb 2025 14:30:03 +0000

Introduction

Welcome back, let’s continue with more 6502 assembly. In the last blog post, the bitmap display was introduced and it will filled with different colours. From that it was discovered that the bitmap display spans from page 2 to page 5 (i.e. $0200 - $0500).

Today an image will be animated through the bitmap display. Below is the starter code provided by Chris Tyler, the instructor of SPO600 course. We’ll continue using the 6502 emulator.

;
; draw-image-subroutine.6502
;
; This is a routine that can place an arbitrary 
; rectangular image on to the screen at given
; coordinates.
;
; Chris Tyler 2024-09-17
; Licensed under GPLv2+
;

;
; The subroutine is below starting at the 
; label "DRAW:"
;

; Test code for our subroutine
; Moves an image diagonally across the screen

; Zero-page variables
define XPOS $20
define YPOS $21

START:

; Set up the width and height elements of the data structure
  LDA #$05
  STA $12       ; IMAGE WIDTH
  STA $13       ; IMAGE HEIGHT

; Set initial position X=Y=0
  LDA #$00
  STA XPOS
  STA YPOS

; Main loop for diagonal animation
MAINLOOP:

  ; Set pointer to the image
  ; Use G_O or G_X as desired
  ; The syntax #<LABEL returns the low byte of LABEL
  ; The syntax #>LABEL returns the high byte of LABEL

  LDA #<G_O
  STA $10
  LDA #>G_O
  STA $11

  ; Place the image on the screen
  LDA #$10  ; Address in zeropage of the data structure
  LDX XPOS  ; X position
  LDY YPOS  ; Y position
  JSR DRAW  ; Call the subroutine

  ; Delay to show the image
  LDY #$00
  LDX #$50
DELAY:
  DEY
  BNE DELAY
  DEX
  BNE DELAY

  ; Set pointer to the blank graphic
  LDA #<G_BLANK
  STA $10
  LDA #>G_BLANK
  STA $11

  ; Draw the blank graphic to clear the old image
  LDA #$10 ; LOCATION OF DATA STRUCTURE
  LDX XPOS
  LDY YPOS
  JSR DRAW

  ; Increment the position
  INC XPOS
  INC YPOS

  ; Continue for 29 frames of animation
  LDA #28
  CMP XPOS
  BNE MAINLOOP

  ; Repeat infinitely
  JMP START

; ==========================================
;
; DRAW :: Subroutine to draw an image on 
;         the bitmapped display
;
; Entry conditions:
;    A - location in zero page of: 
;        a pointer to the image (2 bytes)
;        followed by the image width (1 byte)
;        followed by the image height (1 byte)
;    X - horizontal location to put the image
;    Y - vertical location to put the image
;
; Exit conditions:
;    All registers are undefined
;
; Zero-page memory locations
define IMGPTR    $A0
define IMGPTRH   $A1
define IMGWIDTH  $A2
define IMGHEIGHT $A3
define SCRPTR    $A4
define SCRPTRH   $A5
define SCRX      $A6
define SCRY      $A7

DRAW:
  ; SAVE THE X AND Y REG VALUES
  STY SCRY
  STX SCRX

  ; GET THE DATA STRUCTURE
  TAY
  LDA $0000,Y
  STA IMGPTR
  LDA $0001,Y
  STA IMGPTRH
  LDA $0002,Y
  STA IMGWIDTH
  LDA $0003,Y
  STA IMGHEIGHT

  ; CALCULATE THE START OF THE IMAGE ON
  ; SCREEN AND PLACE IN SCRPTRH
  ;
  ; THIS IS $0200 (START OF SCREEN) +
  ; SCRX + SCRY * 32
  ; 
  ; WE'LL DO THE MULTIPLICATION FIRST
  ; START BY PLACING SCRY INTO SCRPTR
  LDA #$00
  STA SCRPTRH
  LDA SCRY
  STA SCRPTR
  ; NOW DO 5 LEFT SHIFTS TO MULTIPLY BY 32
  LDY #$05     ; NUMBER OF SHIFTS
MULT:
  ASL SCRPTR   ; PERFORM 16-BIT LEFT SHIFT
  ROL SCRPTRH
  DEY
  BNE MULT

  ; NOW ADD THE X VALUE
  LDA SCRX
  CLC
  ADC SCRPTR
  STA SCRPTR
  LDA #$00
  ADC SCRPTRH
  STA SCRPTRH

  ; NOW ADD THE SCREEN BASE ADDRESS OF $0200
  ; SINCE THE LOW BYTE IS $00 WE CAN IGNORE IT
  LDA #$02
  CLC
  ADC SCRPTRH
  STA SCRPTRH
  ; NOTE WE COULD HAVE DONE TWO: INC SCRPTRH

  ; NOW WE HAVE A POINTER TO THE IMAGE IN MEM
  ; COPY A ROW OF IMAGE DATA
COPYROW:
  LDY #$00
ROWLOOP:
  LDA (IMGPTR),Y
  STA (SCRPTR),Y
  INY
  CPY IMGWIDTH
  BNE ROWLOOP

  ; NOW WE NEED TO ADVANCE TO THE NEXT ROW
  ; ADD IMGWIDTH TO THE IMGPTR
  LDA IMGWIDTH
  CLC
  ADC IMGPTR
  STA IMGPTR
  LDA #$00
  ADC IMGPTRH
  STA IMGPTRH

  ; ADD 32 TO THE SCRPTR
  LDA #32
  CLC
  ADC SCRPTR
  STA SCRPTR
  LDA #$00
  ADC SCRPTRH
  STA SCRPTRH

  ; DECREMENT THE LINE COUNT AND SEE IF WE'RE
  ; DONE
  DEC IMGHEIGHT
  BNE COPYROW

  RTS

; ==========================================

; 5x5 pixel images

; Image of a blue "O" on black background
G_O:
DCB $00,$0e,$0e,$0e,$00
DCB $0e,$00,$00,$00,$0e
DCB $0e,$00,$00,$00,$0e
DCB $0e,$00,$00,$00,$0e
DCB $00,$0e,$0e,$0e,$00

; Image of a yellow "X" on a black background
G_X:
DCB $07,$00,$00,$00,$07
DCB $00,$07,$00,$07,$00
DCB $00,$00,$07,$00,$00
DCB $00,$07,$00,$07,$00
DCB $07,$00,$00,$00,$07

; Image of a black square
G_BLANK:
DCB $00,$00,$00,$00,$00
DCB $00,$00,$00,$00,$00
DCB $00,$00,$00,$00,$00
DCB $00,$00,$00,$00,$00
DCB $00,$00,$00,$00,$00

The starter code animates a blue circle at the top left corner of the bitmap display then moves it diagonally to the bottom right corner and repeats indefinitely. To understand how this works, let’s breakdown each routine/subroutine then explain how they work together.

Initial Setup

Zero-Page Variables

; Zero-page variables
define XPOS $20
define YPOS $21

define is a special keyword that defines constants. In this case, XPOS and YPOS represent the respective memory locations for the image’s coordinates.

Positional Setup

START:
  LDA #$05
  STA $12       ; IMAGE WIDTH
  STA $13       ; IMAGE HEIGHT

  LDA #$00
  STA XPOS
  STA YPOS

The image has dimensions of 5x5 and has the initial coordinates of 0,0, the top left corner of the bitmap display.

Main Animation Loop

MAINLOOP:
  LDA #<G_O
  STA $10
  LDA #>G_O
  STA $11

The main animation loops loads the image’s address into the accumulator then stores its low then high byte into the memory locations $10 and $11 respectively.

  ; Place the image on the screen
  LDA #$10  ; Address in zeropage of the data structure
  LDX XPOS  ; X position
  LDY YPOS  ; Y position
  JSR DRAW  ; Call the subroutine

The low byte of the image is loaded in the X and Y coordinates - this is where the DRAW subroutine will start drawing the image into the bitmap display.

Delay

  LDY #$00
  LDX #$50
DELAY:
  DEY
  BNE DELAY
  DEX
  BNE DELAY

The DELAY routine slows down the DRAW routine to display a “solid” image. Without DELAY, the image would flash rapidly. There are 2 loops - an outer loop that increments Y 256 times, and an inner loop that decrements X 80 times. Totalling 80 * 256 = 20480 iterations.

Animating the Image

  ; Set pointer to the blank graphic
  LDA #<G_BLANK
  STA $10
  LDA #>G_BLANK
  STA $11

  ; Draw the blank graphic to clear the old image
  LDA #$10 
  LDX XPOS
  LDY YPOS
  JSR DRAW

  ; Increment the position
  INC XPOS
  INC YPOS

  LDA #28
  CMP XPOS
  BNE MAINLOOP

  ...
; Image of a black square
G_BLANK:
DCB $00,$00,$00,$00,$00
DCB $00,$00,$00,$00,$00
DCB $00,$00,$00,$00,$00
DCB $00,$00,$00,$00,$00
DCB $00,$00,$00,$00,$00

To “animate” the image, the current image turns “blank” by replacing the image with black pixels. The low byte is then loaded into the accumulator, the X and Y position of the image is loaded in their respective registers where they are incremented. The image gets drawn in its new X, Y position - completing the animation. The completes after 29 “movements” then the same animation indefinitely.

`DRAW` Subroutine

The DRAW subroutine is the most important part of the program - it calculates where the image goes at each iteration.

define IMGPTR    $A0
define IMGPTRH   $A1
define IMGWIDTH  $A2
define IMGHEIGHT $A3
define SCRPTR    $A4
define SCRPTRH   $A5
define SCRX      $A6
define SCRY      $A7
...

DRAW:
  STY SCRY
  STX SCRX
  TAY
  LDA $0000,Y
  STA IMGPTR
  LDA $0001,Y
  STA IMGPTRH
  LDA $0002,Y
  STA IMGWIDTH
  LDA $0003,Y
  STA IMGHEIGHT

It starts by loading the position of the screen boundaries, and the image properties (X, Y coordinates, height, and width) from their respective memory addresses and stores them into the predefined register addresses - these values will be accessed later when calculating the position for the next image.

Calculating Screen Position

  LDA #$00
  STA SCRPTRH
  LDA SCRY
  STA SCRPTR
  LDY #$05
MULT:
  ASL SCRPTR
  ROL SCRPTRH
  DEY
  BNE MULT

Calculation Steps:

Clear the accumulator, this is where the calculation will take place
Load the accumulator with the image’s Y-coordinate
The Y-coordinate is then loaded with 5, the number of shifts to move the pixel down since each row is 32 bytes long.
```
1 | 2 | 4 | 8 | 16 | 32 
^ | 2 | 3 | 4 | 5  | 6 
current
```
The MULT routine shifts the the bits to left via ASL and ROL rotates the carry into the SCRPTRH, Y registry is then decremented and repeats until Y = 0.

LDA SCRX
CLC
ADC SCRPTR
STA SCRPTR
LDA #$00
ADC SCRPTRH
STA SCRPTRH

Calculating the X-coordinate introduces addition - where the low byte is added first followed by the high byte. The ADC SCRPTR adds the low byte to the accumulator with carry. This carry value is then added to the high byte with the carry.
At this point, SCRPTR and SCRPTRH hold the final addresses for the transformed image.

Inserting the Transformed Image

LDA #$02
CLC
ADC SCRPTRH
STA SCRPTRH

The bitmap display base address of 02 is loaded, with the carry flag cleared. The screen pointer high byte is set by adding the SCRPTRH calculated in the last step.

COPYROW:
  LDY #$00
ROWLOOP:
  LDA (IMGPTR),Y
  STA (SCRPTR),Y
  INY
  CPY IMGWIDTH
  BNE ROWLOOP

The bytes are copied from IMGPTR to the accumulator, then into SCRPTR which is the memory corresponding the location on the bitmap display. The loop stops when the Y register reaches the end of the image row.

LDA IMGWIDTH
CLC
ADC IMGPTR
STA IMGPTR
LDA #$00
ADC IMGPTRH
STA IMGPTRH
LDA #32
CLC
ADC SCRPTR
STA SCRPTR
LDA #$00
ADC SCRPTRH
STA SCRPTRH

To advance to the next row, the image width is loaded into the accumulator. IMGPTR is then added to the image width, advancing the next row in the image. The updated image pointer is stored in IMGPTR. 32 is by added to SCRPTR in the accumulator then stored back into SCRPTR. The same processes is done with the high byte, with the carry byte.

Bouncing Graphic

Let’s begin by changing the starting position. By loading the accumulator with different values and storing it in XPOS and YPOS.

START:
  LDA #$05
  STA $12       ; IMAGE WIDTH
  STA $13       ; IMAGE HEIGHT

  LDA #$0F
  STA XPOS
  LDA #$0A
  STA YPOS

Next let’s make the graphic bounce once it makes contact with the wall of the bitmap display. To do this we could invert the sign (e.g. +/- ) of the X and Y direction when the graphic makes contact with the wall.

To do this let’s define a constant value to represent the edge of the screen:

; Zero-page variables
define XPOS $20
define YPOS $21
define MAXP $24

Next we need to track the image direction, is it moving “forwards” or “backwards”? In the case it moves “backwards”, the direction can be inverted, and vice versa.

; Zero-page variables
define XPOS $20
define YPOS $21
define MAXP $24
define CURDIR $25

The X and Y sign also need to be tracked to know which direction the respective axes needs to move.

; Zero-page variables
define XPOS $20
define YPOS $21
define MAXP $22
define CURDIR $23
define XFLAG $24
define YFLAG $25

We have the required variables track the movement, now let’s implement the logic of inverting the sign when it reaches the edge.

First let’s initialize CURDIR to have a value of 0 to indicate the forward direction and MAXP #$19, the edge of the screen.

START:
  LDA #$00
  STA CURDIR
  LDA #$19
  STA MAXP

Next let’s implement the case where the image hits the edge with a subroutine:

load the value corresponding to the edge
compare the current XPOS with the edge value
call CHECK_START to check if it hits the top left corner
1. since the signs are inverted, it will always reach the left corner given it’s new starting position.

CHECK_DIRECTION:
  LDA MAXP
  CMP XPOS
  BNE CHECK_START

CHECK_START:
  LDA XPOS
  CMP #$00
  BNE CONTINUE_LOOP
  LDA #$00
  STA CURDIR

CONTINUE_LOOP will check if the animation has finished, and repeat it indefinitely. Let’s look at the code all together.

;
; draw-image-subroutine.6502
;
; This is a routine that can place an arbitrary 
; rectangular image on to the screen at given
; coordinates.
;
; Chris Tyler 2024-09-17
; Licensed under GPLv2+
;

;
; The subroutine is below starting at the 
; label "DRAW:"
;

; Test code for our subroutine
; Moves an image diagonally across the screen

; Zero-page variables
define XPOS $20
define YPOS $21
define MAXP $22 
define CURDIR $23
define XFLAG $24
define YFLAG $25

START:
  LDA #$00
  STA CURDIR

  LDA #$19
  STA MAXP

  ; Set up image width & height
  LDA #$05
  STA $12
  STA $13

  ; Set initial position X=Y=0
  LDA #$09
  STA XPOS
  LDA #$0A
  STA YPOS

MAINLOOP:

  ; Set pointer to the image
  LDA #<G_O
  STA $10
  LDA #>G_O
  STA $11

; Put image on bitmap display
  LDA #$10  
  LDX XPOS  
  LDY YPOS  
  JSR DRAW 

; Delay to show the image
  LDY #$00
  LDX #$50
DELAY:
  DEY
  BNE DELAY
  DEX
  BNE DELAY

  ; Put pointer to blank image
  LDA #<G_BLANK
  STA $10
  LDA #>G_BLANK
  STA $11

  ; Clear previous image position
  LDA #$10  
  LDX XPOS
  LDY YPOS
  JSR DRAW

  LDA CURDIR
  BEQ INCREMENT_POS

  DEC XPOS
  DEC YPOS
  JMP CHECK_DIRECTION

INCREMENT_POS:
  INC XPOS
  INC YPOS

CHECK_DIRECTION:
  LDA MAXP
  CMP XPOS
  BNE CHECK_START

  LDA XPOS
  STA CURDIR
  JMP CONTINUE_LOOP

CHECK_START:
  LDA XPOS
  CMP #$00
  BNE CONTINUE_LOOP
  LDA #$00
  STA CURDIR

CONTINUE_LOOP:
  LDA #28
  CMP XPOS
  BNE MAINLOOP
  ; Repeat infinitely
  JMP START

  ; ==========================================
  ;
  ; DRAW :: Subroutine to draw an image on 
  ;         the bitmapped display
  ;
  ; Entry conditions:
  ;    A - location in zero page of: 
  ;        a pointer to the image (2 bytes)
  ;        followed by the image width (1 byte)
  ;        followed by the image height (1 byte)
  ;    X - horizontal location to put the image
  ;    Y - vertical location to put the image
  ;
  ; Exit conditions:
  ;    All registers are undefined
  ;
  ; Zero-page memory locations
  define IMGPTR    $A0
  define IMGPTRH   $A1
  define IMGWIDTH  $A2
  define IMGHEIGHT $A3
  define SCRPTR    $A4
  define SCRPTRH   $A5
  define SCRX      $A6
  define SCRY      $A7

  DRAW:
    ; SAVE THE X AND Y REG VALUES
    STY SCRY
    STX SCRX

    ; GET THE DATA STRUCTURE
    TAY
    LDA $0000,Y
    STA IMGPTR
    LDA $0001,Y
    STA IMGPTRH
    LDA $0002,Y
    STA IMGWIDTH
    LDA $0003,Y
    STA IMGHEIGHT

    ; CALCULATE THE START OF THE IMAGE ON
    ; SCREEN AND PLACE IN SCRPTRH
    ;
    ; THIS IS $0200 (START OF SCREEN) +
    ; SCRX + SCRY * 32
    ; 
    ; WE'LL DO THE MULTIPLICATION FIRST
    ; START BY PLACING SCRY INTO SCRPTR
    LDA #$00
    STA SCRPTRH
    LDA SCRY
    STA SCRPTR
    ; NOW DO 5 LEFT SHIFTS TO MULTIPLY BY 32
    LDY #$05     ; NUMBER OF SHIFTS
  MULT:
    ASL SCRPTR   ; PERFORM 16-BIT LEFT SHIFT
    ROL SCRPTRH
    DEY
    BNE MULT

    ; NOW ADD THE X VALUE
    LDA SCRX
    CLC
    ADC SCRPTR
    STA SCRPTR
    LDA #$00
    ADC SCRPTRH
    STA SCRPTRH

    ; NOW ADD THE SCREEN BASE ADDRESS OF $0200
    ; SINCE THE LOW BYTE IS $00 WE CAN IGNORE IT
    LDA #$02
    CLC
    ADC SCRPTRH
    STA SCRPTRH
    ; NOTE WE COULD HAVE DONE TWO: INC SCRPTRH

    ; NOW WE HAVE A POINTER TO THE IMAGE IN MEM
    ; COPY A ROW OF IMAGE DATA
  COPYROW:
    LDY #$00
  ROWLOOP:
    LDA (IMGPTR),Y
    STA (SCRPTR),Y
    INY
    CPY IMGWIDTH
    BNE ROWLOOP

    ; NOW WE NEED TO ADVANCE TO THE NEXT ROW
    ; ADD IMGWIDTH TO THE IMGPTR
    LDA IMGWIDTH
    CLC
    ADC IMGPTR
    STA IMGPTR
    LDA #$00
    ADC IMGPTRH
    STA IMGPTRH

    ; ADD 32 TO THE SCRPTR
    LDA #32
    CLC
    ADC SCRPTR
    STA SCRPTR
    LDA #$00
    ADC SCRPTRH
    STA SCRPTRH

    ; DECREMENT THE LINE COUNT AND SEE IF WE'RE
    ; DONE
    DEC IMGHEIGHT
    BNE COPYROW

    RTS

  ; ==========================================

  ; 5x5 pixel images

  ; Image of a blue "O" on black background
  G_O:
  DCB $00,$0e,$0e,$0e,$00
  DCB $0e,$00,$00,$00,$0e
  DCB $0e,$00,$00,$00,$0e
  DCB $0e,$00,$00,$00,$0e
  DCB $00,$0e,$0e,$0e,$00

  ; Image of a yellow "X" on a black background
  G_X:
  DCB $07,$00,$00,$00,$07
  DCB $00,$07,$00,$07,$00
  DCB $00,$00,$07,$00,$00
  DCB $00,$07,$00,$07,$00
  DCB $07,$00,$00,$00,$07

  ; Image of a black square
  G_BLANK:
  DCB $00,$00,$00,$00,$00
  DCB $00,$00,$00,$00,$00
  DCB $00,$00,$00,$00,$00
  DCB $00,$00,$00,$00,$00
  DCB $00,$00,$00,$00,$00

Conclusion

The logic of the lab is simple, but found implementation difficult because of how verbosity of assembly. The verbose nature of assembly has made me appreciate high level languages and how much is hidden.

From the lab, I learned more about the use-cases for subroutines, how and when to implement subroutines into other routines, and BNE statements. This is similar to using “for” loops and “if” statements in high level programming languages.

Overall, I had a difficult time with this lab but in a good way - I questioned what I understood about assembly to this point and challenged my analyzing skills, a transferable skill that goes beyond assembly code. Thanks for reading! See you soon!

Assembly Loops, Bit Shifts, and More!

JP — Tue, 21 Jan 2025 19:20:42 +0000

Introduction

As an introduction to software portability, I get to experiment with 6502 assembly code via an emulator. The lab is focussed on handling bytes located on registries and memory. Processors have a unique set of instructions. A subset of these instructions are manage the memory within, to, and from the registries and memory.

A visualizer can be found in the emulator where each pixel represents a specific address in memory.

Compared to the modern processor the 6502 is a “simple” processor but is still capable. The simplicity of the instruction set serves as a wonderful introduction into writing, understanding, and analyzing the time complexity of assembly code.

; 6502 Instruction Set
ADC AND ASL BCC BCS BEQ BIT
BMI BNE BPL BRK BVC BVS CLC
CLD CLI CLV CMP CPX CPY DEC
DEX DEY EOR INC INX INY JMP
JSR LDA LDX LDY LSR NOP ORA
PHA PHP PLA PLP ROL ROR RTI
RTS SBC SEC SED SEI STA STX
STY TAX TAY TSX TXA TXS TYA

Let’s get started! Here’s a sample of 6502 assembly code given in the lab notes, let’s break it down a couple lines at a time.

    lda #$00
    sta $40
    lda #$02    
    sta $41
    lda #$07
    ldy #$00
 loop:  sta ($40),y
    iny
    bne loop
    inc $41
    ldx $41
    cpx #$06
    bne loop

Understanding 6502 Assembly Code

Before we start looking at the code, let’s understand the 6502 assembly syntax.

#x: represents an immediate operand value.
$: prefix to represents a hexadecimal value.
(): represents an indirect address, accessing memory indirectly by referencing an address in another location.

    lda #$00    ; set a pointer in memory location $40 to point to $0200
    sta $40     ; ... low byte ($00) goes in address $40
    lda #$02    
    sta $41     ; ... high byte ($02) goes into address $41
    lda #$07    ; colour number
    ldy #$00    ; set index to 0

Loading Values into the Registries

The first couple of lines contain 3 unique instructions - lda, sta, ldy. Here’s an overview of each instruction:

Assembly	Name	Description
`lda`	Load Accumulator with Memory	Transfer data from memory into the accumulator register.

Memory → Accumulator register |
| sta | Store Accumulator in Memory | Transfer data from accumulator into memory.

Accumulator register → Memory |
| ldy | Load Index Registry Y from Memory | Transfer data from memory into the Y register.

Y register → Memory |

Lines 1-2 loads 00 into the accumulator registry (i.e. lda #$00), then the accumulator value is stored into the memory location 40 . The same processes is repeated for value 41 . Note that 6502 adopts a little-endian system, where bytes are read from right to left.

Loop

 loop:  sta ($40),y ; set pixel colour at the address (pointer)+Y
    iny     ; increment index
    bne loop    ; continue until done the page (256 pixels)
    inc $41     ; increment the page
    ldx $41     ; get the current page number
    cpx #$06    ; compare with 6
    bne loop    ; continue until done all pages

Let’s review the instructions in this snippet:

Assembly	Name	Description
`iny`	Increment Index Register Y by One	Add one to the current value stored in registry Y.
`bne`	Branch on Result Not Zero	Conditional, branch to an specified address if the Z-flag equals 0.
`inc`	Increment Memory by One	Add one to the contents of the addressed memory location.
`ldx`	Load Index Register X From Memory	Load the index register X from memory.
`cpx`	Compare Index Register X to Memory	Compare the value in the X register with a value in memory or an immediate value.

Inner Loop: Filling the Page with Yellow Pixels

The inner loop starts by calculating where to store the current accumulator value. This is done by adding the value located in the memory address 40 and the value in the y register, which are 00 and 00 respectively. In the first iteration it will fill memory address with the value 07 , stored in the accumulator register, which corresponds to yellow, then do the same with memory address 0201, etc.

Once the loop reaches the max page size of 256, incrementing it will loop back to 00 — flagging the bne instruction to branch off.

Outer Loop: Switching Pages

The outer loop controls which page we are currently on. Remember that we start in page 2 (i.e. 02 ) and is stored in memory address 41 . The outer loops starts by incrementing the page number by 1 via inc $41 and then is loaded into the x register where we check if it equal to 6 (i.e. cpx #$06).

Notice how we start from page 2 and stop at page 5 ( i.e. [2, 6)). Where the page technically gets incremented to the value 6 but cpx $#06 exits the loops, finishing the program instructions.

Now that we understand what the code does, running it will fill the visualizer with yellow pixels!

Code Analysis

Time Complexity

The performance of 6502 assembly code can be quantified by the number of cycles it takes the processor to perform the given instructions. Remember that the 6502 processor has 56 instructions, each of these instructions have a cycle count associated with it.

Below is a table that contain the instruction used in our program with its respective cycle count.

Instruction	Cycles	Cycle Count	Alt Cycles	Alt Count	Total
LDA #$00	2	1	0	0	2
STA $40	3	1	0	0	3
LDA #$02	2	1	0	0	2
STA $41	3	1	0	0	3
LDA #$07	2	1	0	0	2
LDY #$00	2	1	0	0	2
loop: STA ($40), y	6	256	0	0	1536
INY	2	256	0	0	512
BNE loop	3	255	2	1	767
INC $41	5	4	0	0	30
LDX $41	3	4	0	0	18
CPX #06	2	4	0	0	12
BNE loop	3	3	2	1	17

Before we start calculating, let’s understand what each column in the table mean.

Cycles — number of cycles for the instruction to finish executing
Cycle Count — number of times the instruction runs
Alt Cycles — number of additional cycles the instruction runs, depends on specific conditions
Alt Count — number of times the Alt Cycle runs

Initializing Values

The first 6 instructions are only executed once since they “initialize” the starting values of where the memory starts and the offset.

Initializing Values = 14 cycles

Inner Loop

The inner loop starting, lines 7- 9, fill the byte with a yellow pixel, and runs 256 times to fill each byte in the page. However on the 256th iteration, BNE branches giving it a cycle count of 2 instead of 3.

Inner Loop = 255 * (6 + 2 + 3) + 1 * (6 + 2 + 2)
           = 2805 + 10

Note: this calculation is only for a single page.

Outer Loop

The outer loop, lines 10-13, switches the page. However on the last page, BNE branches giving it a cycle count of 2 instead of 3.

Here’s a more in-depth calculation:

Outer Loop = 3 * (5 + 3 + 2 + 3) + 1 * (5 + 3 + 2 + 2)
           = 31 + 12
           = 51 cycles

Total

Putting it all together:

Total = Initializing Values + Inner Loop * 4 Pages + Outer Loop
      = 14 + (2815 * 4) + 51
      = **11325 cycles**

Performance

The 6502 processor runs at a clock speed of 1Mhz, where each cycle takes 1 microsecond to complete. Let’s calculate the programs performance.

Program cycle count = 11325 Cycles
Clock Speed = 1 Mhz
===================================
Time to complete = Program cycle count / Clock speed (Hz)
                 = 11325 Cycles / (1000000 Cycles / second)
                   = 0.011325 seconds

Time to complete = 0.011325 seconds = 11.325 milliseconds

Memory Complexity

The 6502 processor has a total of 256 pages where each page has 256 bytes, with a grand total of 65536 bytes of memory. Note that page 0 is optimized for 0 page addressing and page 1 is reserved for the stack.

Our program is utilizing the memory in 3 ways — the assembly instructions, written values, and pointer memory.

Assembly Instructions

Each instruction in the program uses memory when executed, below is the associated memory to the instructions in the program.

Instruction	Bytes
LDA #$00	2
STA $40	2
LDA #$02	2
STA $41	2
LDA #$07	2
LDY #$00	2
loop: STA ($40), y	2
INY	1
BNE loop	2
INC $41	2
LDX $41	2
CPX #06	2
BNE loop	2

Assembly instruction memory = 2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 + 2 + 2 + 2 + 2 + 2
                           = 25 bytes

Summing the bytes from each instruction is a total of 25 bytes

Written Values

As we’ve seen multiple times, the program stores 07 into all the bytes of pages 2 to 5, and each page is 256 bytes.

Written values memory = 256 * 4
                                         = 1024 bytes

The program writes to 1024 bytes

Pointers

In the beginning of the program we dedicate memory for the pointers to store the base address (i.e. $40 and $41).

Pointer memory = 1 + 1 
               = 2

Total Memory

Adding each of the ways the program uses memory, we have a grand total of 1051 bytes of memory.

Total memory usage = Assembly instructions + Written values + Pointers
                   = 25 + 1024 + 2
                   = 1051 bytes

Optimization and Modification

Optimization

The current code uses 2 loops, one to go through each address in the current and another to increment the page. Notice that each page has the same number of addresses, therefore, we can use the offset to set the pixel for all 4 pages at the same. This works because the low-byte of each address is the same for each page, and since we know which pages map to the bitmap visualizer we can use the absolute value, rather than a reference.

    lda #$07        ; Set color yellow
    ldy #$00        ; Start with offset of 0

loop:
    sta $0200, y    ; Set pixel for page 2
    sta $0300, y    ; Set pixel for page 3
    sta $0400, y    ; Set pixel for page 4
    sta $0500, y    ; Set pixel for page 5
    iny             ; Increment the offset

    bne loop        ; Loop until overflow back to 00

Note that there is a single loop, reducing the runtime significantly. In terms of Big O notation, this reduces the runtime from O(n^2) to O(n). Let’s calculate the number of cycles.

Instruction	Cycles	Cycle Count	Alt Cycles	Alt Count	Total
LDA #$07	2	1	0	0	2
LDA #$00	2	1	0	0	2
loop: STA $0200, y	5	256	0	0	1280
loop: STA $0300, y	5	256	0	0	1280
loop: STA $0400, y	5	256	0	0	1280
loop: STA $0500, y	5	256	0	0	1280
INY	2	256	0	0	512
BNE loop	3	3	2	1	767

Total Cycles = 2 + 2 + (1280 * 4) + 512 + 767
             = **6403 cycles**

Percentage Reduction = (Original Cycle Count - Optimized Cycle Count) / Original Cycle Count) * 100
                     = (11325 - 6403) / 11325 * 100
                     = 0.4356 * 100
                     = **43.46 %**

With the optimization, cycle count has been reduced by approximately 43%! In my opinion, the code does look cleaner, but as instructions get more complex, the absolute values addressing the pages may not work.

Modifications

Modification 1: Change the Pixels to Light Blue

The value for light blue can be found in the “Notes” output in the console. $e corresponds to light blue. Let’s change the accumulator value to $e in our optimized code and observe the difference.

    lda $0e        ; Set color light blue
    ldy #$00        ; Start with offset of 0

loop:
    sta $0200, y    ; Set pixel for page 2
    sta $0300, y    ; Set pixel for page 3
    sta $0400, y    ; Set pixel for page 4
    sta $0500, y    ; Set pixel for page 5
    iny             ; Increment the offset

    bne loop        ; Loop until overflow back to 00

Modification 2: Different Colours for each Page

We can modify the original code to use the high-byte value for the colour code rather than a static value. Therefore, the first page (page 2) will use colour value $02 which is a red, then page 3 will use colour value $03 which is cyan, etc.

    lda #$00       ; Set pointer to $0200
    sta $40        ; Low byte in $40
    lda #$02       ; Set high byte of the pointer
    sta $41        ; High byte in $41
    ldy #$00       
loop:   
    lda $41        ; Use high byte as the color code
    sta ($40),y    ; Set pixel color at (pointer)+Y using high byte
    iny            ; Increment Y index
    bne loop       

    inc $41        ; Increment page
    cmp #$06       
    bne loop

Modification 2: Random Colour for each Pixel

We can modify the original code to generate a random colour in each iteration. From the “Notes” section from the emulator,
* Memory location $fe contains a new random byte on every read.

$fe can be used to get a random byte (i.e. colour) at each iteration.

      lda #$00        ; Set a pointer in memory location $40                                           
      sta $40         ; Low byte ($00) goes in address $40
      lda #$02        ; High byte ($02) goes into address $41
      sta $41
      ldy #$00        ; Set index to 0

loop: sta ($40), y    ; Set pixel color at the address 
                      ;  (pointer)+Y
      lda $fe     ; get a random color
      iny         ; Increment index
      bne loop    ; Continue until done the page (256 pixels)
      inc $41     ; Increment the page
      ldx $41     ; Get the current page number
      cpx #$06    ; Compare with 6
      bne loop    ; Continue until done all pages

Experiments

Now that we understand the assembly code, lets perform a number of experiments.

Experiment 1: `tya` Instruction

Let’s begin by adding tya , transfer index Y to accumulator, instruction to the inner loop.

    lda #$00    ; set a pointer in memory location $40 to point to $0200
    sta $40     ;  low byte ($00) goes in address $40
    lda #$02    
    sta $41     ;  high byte ($02) goes into address $41
    lda #$07    ; colour number
    ldy #$00    ; set index to 0
 loop:  tya ; ** NEW **, transfer index Y into accumulator
  sta ($40),y   ; set pixel colour at the address (pointer)+Y
    iny     ; increment index
    bne loop    ; continue until done the page (256 pixels)
    inc $41     ; increment the page
    ldx $41     ; get the current page number
    cpx #$06    ; compare with 6
    bne loop    ; continue until done all pages

With a single instruction, we change the result to have vertical stripes of repeating colours, starting with black, white, burgundy, aqua, etc. Monitoring the memory starting at 0200, we can see the pattern in the values stored in each page:

       0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
0200: 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
0210: 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f
0220: 20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f
0230: 30 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f
0240: 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f
0250: 50 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f
0260: 60 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f
0270: 70 71 72 73 74 75 76 77 78 79 7a 7b 7c 7d 7e 7f
0280: 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f
0290: 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f
02a0: a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 aa ab ac ad ae af
02b0: b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf
02c0: c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 ca cb cc cd ce cf
02d0: d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 da db dc dd de df
02e0: e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 ea eb ec ed ee ef
02f0: f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 fa fb fc fd fe ff

In the assembly code, the value in the Y register is loaded into the accumulator, replacing the the initial value of 07. Entering the loop, the Y value is now used as both the low byte, and the page offset — this can be seen in the matrix above, where the column value (i.e. offset value) is the same as the low byte.

If we look at the notes section of the simulator the Y value corresponds to the colour on the visualizer.

$0: Black
$1: White
$2: Red
...
$d: Light green
$e: Light blue
$f: Light grey

Experiment 2: `lsr` Instruction

Let’s add the lsr, logical shift right, instruction immediately after tya added in the previous experiment

    lda #$00    ; set a pointer in memory location $40 to point to $0200
    sta $40     ; low byte ($00) goes in address $40
    lda #$02    
    sta $41     ; high byte ($02) goes into address $41
    lda #$07    ; colour number
    ldy #$00    ; set index to 0
 loop:  tya ; transfer index Y into accumulator
  **lsr ; ** NEW **, logical shift right**
  sta ($40),y   ; set pixel colour at the address (pointer)+Y
    iny     ; increment index
    bne loop    ; continue until done the page (256 pixels)
    inc $41     ; increment the page
    ldx $41     ; get the current page number
    cpx #$06    ; compare with 6
    bne loop    ; continue until done all pages

With lsr, instead of each colour appearing twice, each colour appears only once with each vertical line being 1 pixel wider. By default, lsr shifts the accumulator value to the right by 1 bit. This behaviour can be seen when monitoring the pages:

       0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
0200: 00 00 01 01 02 02 03 03 04 04 05 05 06 06 07 07
0210: 08 08 09 09 0a 0a 0b 0b 0c 0c 0d 0d 0e 0e 0f 0f
0220: 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17
0230: 18 18 19 19 1a 1a 1b 1b 1c 1c 1d 1d 1e 1e 1f 1f
0240: 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27
0250: 28 28 29 29 2a 2a 2b 2b 2c 2c 2d 2d 2e 2e 2f 2f
0260: 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37
0270: 38 38 39 39 3a 3a 3b 3b 3c 3c 3d 3d 3e 3e 3f 3f
0280: 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47
0290: 48 48 49 49 4a 4a 4b 4b 4c 4c 4d 4d 4e 4e 4f 4f
02a0: 50 50 51 51 52 52 53 53 54 54 55 55 56 56 57 57
02b0: 58 58 59 59 5a 5a 5b 5b 5c 5c 5d 5d 5e 5e 5f 5f
02c0: 60 60 61 61 62 62 63 63 64 64 65 65 66 66 67 67
02d0: 68 68 69 69 6a 6a 6b 6b 6c 6c 6d 6d 6e 6e 6f 6f
02e0: 70 70 71 71 72 72 73 73 74 74 75 75 76 76 77 77
02f0: 78 78 79 79 7a 7a 7b 7b 7c 7c 7d 7d 7e 7e 7f 7f

lsr shifts the bits to the right by removing the right most bit and in this case, inserts a 0 to the left most position. If we walk-through the first 3 iterations:

Iteration 1:
1. Y = A = 00 → 00 = 0000 0000
2. After lsr: 00 = 0000 0000 → 00 = 0000 0000
  1. Note: nothing changes
Iteration 2:
1. Y = A = 01 → 01 = 0000 0001
2. After lsr: 01 = 0000 0001 → 00 = 0000 0000
Iteration 3:
1. Y = A = 02 → 02 = 0000 0010
2. After lsr: 02 = 0000 0010 → 01 = 0000 0001

These calculated values correspond their respective memory addresses. (e.g. 0200 - 0202).

Experiment 2a: Repeating `lsr` Instructions

Let’s repeat the lsr instructions multiple times. Given what we know about lsr, the bits should shift x amount of times to the right, where x is the number of repeated lsr instructions.

Initially, I thought repeating lsr once will (i.e. 2 lsr in succession) will widen the lines by a factor of 2 but I was partly wrong. If we look at the image the same way the program loops, moving left to right, then top to bottom, we see that the colours are doubling in width. What I didn’t expect is the alternating pattern of colours.

The alternating colour pattern is due to right shift, where the width would increase 2^x times before going to the next colour.

Let’s repeat this with 3 to 5 lsr instructions in succession. Given our observations, we should see the colour cover 8, 16, then 32 pixels wide, before going to the next colour.

3 lsr

4 lsr

5 lsr

If we observe closely, the pattern is always black, white, burgundy, cyan, etc.

Experiment 2a: Repeating `asl` Instructions

Let’s repeat the lsr experiment but replace lsr with asl. asl, arithmetic shift left, shifting the bits to the left once. It completes this in a similar way, where the right most bit is removed and in this case a 0 is inserted to the most right.

Let’s run through the first 3 iterations where one asl is in the loop:

Iteration 1:
1. Y = A = 00 → 00 = 0000 0000
2. After asl: 00 = 0000 0000 → 00 = 0000 0000
  1. Note: nothing changes
Iteration 2:
1. Y = A = 01 → 01 = 0000 0001
2. After asl: 01 = 0000 0001 → 02 = 0000 0010
Iteration 3:
1. Y = A = 02 → 02 = 0000 0010
2. After asl: 02 = 0000 0100 → 04 = 0000 0100

This pattern can be observed in the memory map:

       0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
0200: **00 02 04** 06 08 0a 0c 0e 10 12 14 16 18 1a 1c 1e
0210: 20 22 24 26 28 2a 2c 2e 30 32 34 36 38 3a 3c 3e
0220: 40 42 44 46 48 4a 4c 4e 50 52 54 56 58 5a 5c 5e
0230: 60 62 64 66 68 6a 6c 6e 70 72 74 76 78 7a 7c 7e
0240: 80 82 84 86 88 8a 8c 8e 90 92 94 96 98 9a 9c 9e
0250: a0 a2 a4 a6 a8 aa ac ae b0 b2 b4 b6 b8 ba bc be
0260: c0 c2 c4 c6 c8 ca cc ce d0 d2 d4 d6 d8 da dc de
0270: e0 e2 e4 e6 e8 ea ec ee f0 f2 f4 f6 f8 fa fc fe
0280: 00 02 04 06 08 0a 0c 0e 10 12 14 16 18 1a 1c 1e
0290: 20 22 24 26 28 2a 2c 2e 30 32 34 36 38 3a 3c 3e
02a0: 40 42 44 46 48 4a 4c 4e 50 52 54 56 58 5a 5c 5e
02b0: 60 62 64 66 68 6a 6c 6e 70 72 74 76 78 7a 7c 7e
02c0: 80 82 84 86 88 8a 8c 8e 90 92 94 96 98 9a 9c 9e
02d0: a0 a2 a4 a6 a8 aa ac ae b0 b2 b4 b6 b8 ba bc be
02e0: c0 c2 c4 c6 c8 ca cc ce d0 d2 d4 d6 d8 da dc de
02f0: e0 e2 e4 e6 e8 ea ec ee f0 f2 f4 f6 f8 fa fc fe

1 asl

One interesting observation are the differences in colours between asl and lsr. Since we are shifting bits to the left, the colour values are increasing by a factor of 2 (e.g. 2x where x is the number of asl instructions in succession).

The values resulting in asl will always be of base 2, which explains the colour pattern of black ($0), red ($2), purple ($4), etc. with 1 asl the pattern ends with blue ($e). Given the pattern, I expect the pattern to shorten by a factor of 2 because each value will be doubled (e.g. $02 → $04, $04 → $08, etc.).

Let’s continue by adding the remaining asl instructions:

2 asl

3 asl

4 asl

5 asl

Notice at 4 and 5 asl, it is filled with all black pixels. Shifting bits the to left 4+ times will being the value into the second byte, leaving the first byte to the filled with 0’s. For example let’s apply asl 4 times to 01.

01 = 0000 0001 → 10 = 0001 0000. The second byte will be displayed in the bitmap visualizer, with 0 being a black pixel. We can see that the 1 that starting in the first byte has been shifted into the second byte - leaving the first byte to be replaced with all 0’s.

Experiment 3: Repeating `iny` Instructions

We’ve seen iny in the previous section where it was used to increment the memory address of a page. Let’s add more iny instructions and observe the bitmap visualizer changes.

2 iny

3 iny

4 iny

5 iny

One key observation is the run animation of the when there are odd number of iny instructions. With 3, each page is being passed through 3 times before moving to the next page. The same observation is made when there are 5 iny instructions, where a page would be passed through 5 times before moving to the next page.

When it comes to even number of iny instructions, the bitmap displays vertical stripes but the larger the step, the wider the black stripe becomes.

This pattern can be understood by the relationship by calculating the modulus. Let’s use 3 and 2. 255 mod 3 = 0, with no remainder it means all memory addresses will be filled. 255 mod 2 = 1, with a remainder of 1, it means that every other memory address is skipped. This explains why we get a vertical stripe pattern with even numbers.

Conclusion

In this lab, we wrote some assembly to understand the flow of data between registers, and memory! Comparing assembly to high level programming languages (e.g. Python, JavaScript), a lot can go wrong since there isn’t a “safety” net that warns you about potential issues before running the code.

Dealing with memory in general can be tricky since you need to facilitate the movement, allocation, and deallocation. With my current knowledge I expect memory management strategies to be similar to C/C++.

The shifting of bits to the left or right was a completely new concept and found it interesting how such a “small” change is responsible for a large change, in this lab it can change an pixel to a completely different colour. I imagine in larger, complex programs, bit shifting can cause a catastrophic event. I’m excited to use this knowledge in preparation for the next lab! See you soon!

New Beginnings: SPO600

JP — Mon, 13 Jan 2025 16:22:20 +0000

Introduction

When selecting my courses for my last semester, I saw “SPO600 - Software Portability and Optimization” and thought to myself - this is a good opportunity to step out of comfort zone of web technologies and learn about how software “works under the hood”.

After reading the course description and I Googled “what is software portability?” One of the top answers were: “the ability of software to be efficiently used across different environments without losing functionality or quality.” Through continued self research, portability deals with the “nitty-gritty” of code - where the code we write in high-level languages gets translated into machine code, which is specific to the architecture of the machine it is being run on.

We interact with software everyday and most of us, myself included, don’t think twice about how and why it works? By the end of this course I want to understand “How do multi-platforms apps/games work?”, “How do game emulators work?”, “Why are some programming languages ‘faster’ than others?”. Of course these are a handful of questions I have but I believe I will have more interesting ones as the course progresses!

I’ll have more updates soon!

Jon

Reference: Ram, J. (n.d.). Figure showing the translation of high-level language into machine code. Retrieved from https://www.cs.trincoll.edu/~ram/jjjnotes/ch0/img2.gif

DEV Community: JP

SPO600 Project Stage 3: Wrapping it Up

Introduction

Finding Multiple Function Versions of a Cloned Function

Creating a Function “Fingerprint”

Recording a Function “Fingerprint”

Test Cases

Unrolling 4 Units

Arithmetic Operation

Performing the Tests

Results

Discussion

Limitations

1.Assumption of Same Control Flow for Comparison

2. Hard-Coded Assumptions in Function Name Processing

3. Potential for Incorrect Handling of Debugging Information

Conclusion

SPO600 Project Stage 2, Part 3: “Prune Away!”

Introduction

Comparing Function Fingerprints

Putting it all Together

Results

Setup

Test Results

Reflection

Conclusion

SPO600 Project Stage 2, Part 2: "Where Art Thou, Clones?"

Introduction

Identifying the Function Variants

Identifying the Base Function

Fingerprinting Functions

Putting it Together

Results

Setup

Test Results

Reflection

Conclusion

SPO600 Project Stage 2, Part 1: “To Prune, or not to Prune”

Introduction

Gameplan

Background

Steps

Conclusion

SPO600 Project Stage 1: Gimple and Passes

Introduction

GIMPLE

Passes

Setup and Execution

Overview

Creating the Pass

Namespace and Pass Metadata

Custom Pass Class pass_japablo

Factory Function for the Pass

Registering the Pass

Modifying tree-pass.h

Updating the Makefile

Rebuilding gcc

Results

Dump File

Conclusion

SPO600 Lab 5 - Analyzing and Experimenting with Assembly

Introduction

Preparing the Lab Environment

aarch64

Loops

Loop with Iteration Number

Loop to 32

Loop to 32 Without Trailing 0’s

Looping to 32 with Hex Values

x86

Results

Extracting Tens and Ones

Conclusion

SPO600 Lab 4 - x86 GCC vs aarch64 GCC

Introduction

GCC

Lab 4

Predictions

Possible Issues

Setup

`GIMPLE`

Custom Pass Class `pass_japablo`

Modifying `tree-pass.h`

Updating the `Makefile`

Rebuilding `gcc`

`aarch64`

`x86`

`GCC`

Verify `GCC` Compilation

`GETKEY`

`CHECKENTER`

`CHECKCOUNT`

`CHECKLETTER`

`DRAW` Subroutine

Experiment 1: `tya` Instruction

Experiment 2: `lsr` Instruction

Experiment 2a: Repeating `lsr` Instructions

Experiment 2a: Repeating `asl` Instructions

Experiment 3: Repeating `iny` Instructions