Call graph

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Call graph

Post by tepples »

As programs grow in complexity, tools to manage this complexity become more and more useful. I'm working on a tool written in Python to generate a context-insensitive static call graph of a ca65 program consisting of multiple translation units (.s files).

A "far call" happens when a subroutine in one PRG bank calls a subroutine in another. On some mappers, especially MMC1, a far call takes quite a few cycles to complete, so you can't just toss a small, often-used subroutine in one bank and expect the rest of the program to far call it. And on mappers with 32 KiB PRG bank switching, you can't toss it in a fixed bank either, so you have to either A. duplicate it in all banks containing a subroutine that calls it or B. move all subroutines that call it to the same bank. You can get an idea for what to do based on the call graph.

On a few mappers, the NMI handler needs special consideration. It can be thought of as a subroutine that every other subroutine in the program calls. Mappers with 32 KiB PRG bank switching need at least some of the NMI handler to be duplicated in each bank. MMC1 has a quirk that the NMI handler can't save and restore the entire state of the mapper. Therefore, you usually want to make sure that everything the NMI handler needs is in the fixed bank or in RAM. This becomes more difficult if your NMI handler runs the entire music engine. So you'd look at the call graph to see what the NMI handler is calling and what bank it needs to be in.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Call graph

Post by tokumaru »

tepples wrote:MMC1 has a quirk that the NMI handler can't save and restore the entire state of the mapper. Therefore, you usually want to make sure that everything the NMI handler needs is in the fixed bank or in RAM.
This is one of the reasons I hate the MMC1. There are workarounds though... You could set a flag before bankswitching in the main thread, so that interrupts that also need to bankswitch can detect whether they interrupted a mapper write. In that case, they'd modify that flag and return to let the mapper operation finish, at which point the main thread would be able to detect what happened by checking the flag, and it could resume the interrupt. This is far from ideal though, and makes makes writes even slower than they already are on that mapper.

As for call graphs, I don't know enough about them to tell if they're worth the trouble. I sure had to figure out a lot of inter-bank calls when designing my game, but I didn't need to analyze how every little routine was called... Dividing them in groups was enough to get a good idea on how the ROM would have to be organized.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples »

For example, here's the call graph of Thwaite:
56K warning, and over 17,000 pixels wide
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Call graph

Post by tepples »

tokumaru wrote:Dividing them in groups was enough to get a good idea on how the ROM would have to be organized.
Good idea. I've taken a first stab at grouping things. First I grouped symbols referred to in only one place with their only caller, and from there I was able to find enough "functional units" to cut the graph roughly in half. I ended up finding a few places where I might need to reorganize the program itself for less coupling.

http://pics.pineight.com/nes/thwaitecalls_grouped.png
(still 56K warning, but only about 9,000 pixels wide now)
Attachments
thwaitecalls_grouped.png
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Call graph

Post by tepples »

Someone in another topic requested the program I wrote to make these call graphs. It requires Python 2 and GraphViz.
Attachments
callgraph.py.zip
(3.76 KiB) Downloaded 443 times
pops
Posts: 91
Joined: Sun Apr 04, 2010 4:28 pm

Re: Call graph

Post by pops »

tepples wrote:
tokumaru wrote:Dividing them in groups was enough to get a good idea on how the ROM would have to be organized.
Good idea. I've taken a first stab at grouping things. First I grouped symbols referred to in only one place with their only caller, and from there I was able to find enough "functional units" to cut the graph roughly in half. I ended up finding a few places where I might need to reorganize the program itself for less coupling.

http://pics.pineight.com/nes/thwaitecalls_grouped.png
(still 56K warning, but only about 9,000 pixels wide now)
That call graph is exceptionally cool! I could have used something like that when I was returning to work on the NES project I was working on during the spring. Would it work on a project that hadn't been written for the ca65 assembler?

I have a tendency to leave my code uncommented - which means that figuring out how a given function works is difficult if I haven't worked on it in a month. This is doubly true with 6502 code. In order to figure out how everything worked together, I had to audit my code, practically line by line.

Lesson learned: I now have comments on about 1/2 of the lines of code, and I've documented my data formats in tedious detail.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Call graph

Post by tepples »

pops wrote:Would it work on a project that hadn't been written for the ca65 assembler?
The parser might need to be changed to work with NESASM or ASM6 or WLA syntax.
I have a tendency to leave my code uncommented - which means that figuring out how a given function works is difficult if I haven't worked on it in a month.
Read about how to write effective javadoc style comments at the top of each subroutine, and you'll have a target to shoot for.
Post Reply