It is currently Mon Dec 17, 2018 1:12 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 7 posts ] 
Author Message
 Post subject: Call graph
PostPosted: Thu Dec 22, 2011 11:51 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20887
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
 Post subject: Re: Call graph
PostPosted: Thu Dec 22, 2011 6:39 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11013
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
 Post subject:
PostPosted: Wed Dec 28, 2011 4:41 pm 
Offline

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


Top
 Profile  
 
 Post subject: Re: Call graph
PostPosted: Thu Jan 05, 2012 3:39 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20887
Location: NE Indiana, USA (NTSC)
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)


Top
 Profile  
 
 Post subject: Re: Call graph
PostPosted: Tue Jul 08, 2014 10:18 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20887
Location: NE Indiana, USA (NTSC)
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 185 times
Top
 Profile  
 
 Post subject: Re: Call graph
PostPosted: Wed Jul 09, 2014 11:06 am 
Offline

Joined: Sun Apr 04, 2010 4:28 pm
Posts: 91
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.


Top
 Profile  
 
 Post subject: Re: Call graph
PostPosted: Wed Jul 09, 2014 12:58 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20887
Location: NE Indiana, USA (NTSC)
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.

Quote:
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group