I'm running into a bug in my code where the address of a local stack variable is invalid. I've been trying to debug this with lldb.
In the lldb prompt below, you can see that &dominance_frontier gives the address
0x0000000000000001 which then causes a SIGSEGV on hash_table_init call line 121.
However &dominator_tree_adj, gives a valid address. I'm completely baffled as to
why this might be the case.
Process 70998 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = step over
frame #0: 0x0000000100006fd0 ir`ComputeDominanceFrontier(function=0x00006000030f8000) at dominators.c:121:9
111 struct Array postorder_traversal = postorder (function->entry_basic_block);
112 struct DFAConfiguration config = DominatorDFAConfiguration (function);
113 struct DFAResult result = run_DFA (&config, function);
114
115 HashTable dominator_tree_adj = ComputeDominatorTree (function, &result);
116 printf("%p\n", &dominator_tree_adj);
117 HashTable dominance_frontier;
118 printf("%ld\n", sizeof(dominance_frontier));
119
120
-> 121 hash_table_init (&dominance_frontier);
122 // Compute the transpose graph from the dominator tree adjacency list
123 // Each node is guaranteed to have only one direct predecessor, since
124 // each node can only have one immediate dominator. We will need this
125 // in the DF algorithm below
126 HashTable dominator_tree_transpose;
127 hash_table_init (&dominator_tree_transpose);
128
129 struct HashTableEntry *entry;
130 size_t entry_iter = 0;
131
Target 0: (ir) stopped.
(lldb) p &dominance_frontier
(HashTable *) 0x0000000000000001
(lldb) p &dominator_tree_adj
(HashTable *) 0x000000016fdfef38
I've been compiling my code with make DEBUG=yes
OPT = -O3
FLAGS = -Wall -Wextra
CC = cc
OBJECTS = ir_parser.o \
main.o \
threeaddr_parser.o \
instruction.o \
function.o \
basicblock.o \
constant.o \
utils.o \
value.o \
array.o \
mem.o \
map.o \
dfa.o \
dominators.o
ifdef DEBUG
OPT = -g
else
OPT = -O3
endif
all: $(OBJECTS)
$(CC) $(OPT) $(FLAGS) $^ -o ir
%.o: %.c *.h
$(CC) $(OPT) $(FLAGS) -c $< -o $@
clean:
rm *.o
This is the location of the segfault:
Process 10619 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x9)
frame #0: 0x0000000100005060 ir`_hash_table_init(table=0x0000000000000001, size=10) at map.c:21:21
11 // Open addressing, linear probe hash table.
12
13 unsigned long uint64_t_hash_function (uint64_t key)
14 {
15 // Simple hash function for demonstration
16 return key;
17 }
18
19 void _hash_table_init (HashTable *table, size_t size)
20 {
-> 21 table->size = size;
22 table->count = 0;
23 table->buckets = ir_calloc (table->size, sizeof (HashTableEntry));
24 }
25 void hash_table_init (HashTable *table)
26 {
27 _hash_table_init (table, MAP_INIT_SIZE_CNT);
28 }
29
30 // Create a new hash table
31 HashTable *hash_table_create (size_t size)
Target 0: (ir) stopped.
Input file:
fn test4(%1, %2) {
alloca %9, 5
add %3, %1, %2
store %9, %3
cmp %4, %1, %2
jumpif 1, %4
sub %5, %3, 1
jumpif 2, %5
1:
add %6, %1, 20
jump 3
2:
add %7, %2, 30
3:
sub %8, %3, %3
}
./ir -f path/to/input/file
I'm using Apple clang version 15.0.0 (clang-1500.3.9.4)
Full code is here: https://github.com/CoconutJJ/compiler-optimization/blob/d3244e8c9f96e8180c924533abf8f5daac15238c/ir/dominators.c#L115
HashTable ComputeDominanceFrontier (struct Function *function)
^^^^^^^^^
void ComputeDominanceFrontier (struct Function *function);
^^^^
Oopsie.
The function ComputeDominanceFrontier is called from main.c which includes dominators.h, so the caller thinks that it returns void. But according to the definition in dominators.c, it actually returns HashTable. This mismatch is the cause of the crash, as explained below.
The compiler does not catch this because you did not include dominators.h into dominators.c, so when compiling dominators.c, it had no idea that some other source file was seeing a conflicting declaration. For this reason, when a header declares a global function, you should always make sure that header is included into the source file that defines the function. You can help enforce this with -Wmissing-prototypes, which gives a warning whenever a global function is defined without having previously been declared. See Compiler warning for function defined without prototype in scope?
What happens is this: on arm64, like many other platforms, when a function returns a struct type that can't be returned in a register, it's returned by "hidden reference": the caller allocates space for the return value, and passes an extra hidden argument with the address of that space. On arm64 the extra argument is passed in register x8. Then the called function is responsible for copying its return value into that space.
In this case, since main didn't know that ComputeDominanceFrontier was returning a struct type, it didn't allocate such space, and left x8 containing garbage (in your case, its value happened to be 1).
If compiled naively, you would then expect to see a crash at the end of the function, when dominance_frontier is copied from the stack into the bogus return value address. And it sounds like that's what you did see in your Ubuntu test (which, let me guess, used gcc instead of clang?).
However, the compiler can optimize this: instead of using stack space for dominance_frontier, use the return value space allocated by the caller. Then we don't need to copy that data before returning, because it was populated "in place". It appears that clang performs this optimization even when optimizations are "off". So as such, dominance_frontier doesn't really live on ComputeDominanceFrontier's stack frame, and &dominance_frontier isn't a stack address but rather the return value address passed by the caller - which in this case is garbage.