Here's a very simplified overview of how IDA does it:
- add to the analysis queue all known entrypoints, or addresses specified by the user
- while queue not empty, pop the next address
- ask processor module to disassemble the instruction
- ask processor module to analyze the instruction
- processor module adds code cross-references to all possible targets
in the simplest case, it's the next instruction
for conditional jumps and calls, it's the next instruction and the target
for indirect jumps - unknown, unless it's a recognized switch pattern
- put not-yet analyzed targets of all those cross-references into the queue
- go to step 2
Of course, in reality things are more complex. To start with, there's not a single queue but several. From the SDK's
// This file contains functions that work with the autoanalyzer
// queue. The autoanalyzer works when IDA is not busy processing
// the user keystrokes.
// The autoanalyzer has several queues. Each queue has its priority.
// A queue contains addresses or address ranges.
// The addresses are kept sorted by their values.
// The analyzer will process all addresses from the first queue, then
// switch to the second queue and so on.
// There are no limitations on the size of the queues.
// The analyzer stops when all queues are empty.
// Also this file contains functions that deal with the IDA status
// indicator and the autoanalysis indicator.
// You may use these functions to change the indicator value.
// Names and priorities of the analyzer queues
typedef int atype_t;
const atype_t // priority, description
AU_NONE = 00, // placeholder, not used
AU_UNK = 10, // 0 convert to unexplored
AU_CODE = 20, // 1 convert to instruction
AU_WEAK = 25, // 2 convert to instruction (ida decision)
AU_PROC = 30, // 3 convert to procedure start
AU_TAIL = 35, // 4 add a procedure tail
AU_TRSP = 38, // 5 trace stack pointer (not used yet)
AU_USED = 40, // 6 reanalyze
AU_TYPE = 50, // 7 apply type information
AU_LIBF = 60, // 8 apply signature to address
AU_LBF2 = 70, // 9 the same, second pass
AU_LBF3 = 80, // 10 the same, third pass
AU_CHLB = 90, // 11 load signature file (file name is kept separately)
AU_FINAL=200; // 12 final pass