Compiler-module-scheduler

Overview

edit

This page is about the compiler's internal scheduler for compiling and loading ppu files.

Basic tasks

edit

fpc takes one source file as cmd line parameter, which becomes the main_module (a tppumodule), where main_module.is_initial=true. The main module is always compiled (ignoring any existing ppu).

Then it starts the scheduler of unit ctask.

Compiling a pascal source

edit
  1. Has a state consisting of scanner, parser, symtablestack etc.
  2. Depending on platform and options some implicit units are loaded. At least the system unit. At the moment implicit units are not scheduled, instead a simple loop loads them.
  3. Then it starts parsing. If there is a $mode directive it might load the objpas or macpas module.
  4. If there is a uses section it is parsed and then it loads the units of the uses section. In a unit in_interface is true, otherwise false. If there are any cycles it stops, sets state to ms_compiling_waitintf (ms_compiling_wait for non unit) and returns to the scheduler. At this point the current_module.used_units contains links to all used units (tppumodule). The scheduler later invokes this point again.
  5. Then it adds the globalsymtables of the used units to the symtablestack
  6. Parsing continues
  7. In a unit:
    1. at the implementation keyword it sets current_module.interface_compiled to true and computes the interface_crc and indirect_crc.
    2. parsing the optional implementation uses section. As above if there are any cycles it stops, sets state to ms_compiling_waitimpl and returns to the scheduler. The scheduler later calls this again.
    3. Then it adds the globalsymtables of the used units to the symtablestack
  8. after parsing some extra implicit units are loaded, e.g. the variants unit. Again, not scheduled, using a simple loop.
  9. In a unit:
    1. If there are pending modules (e.g. a specialization waits for a generic of another module) it sets state to ms_compiling_waitfinish and returns to the scheduler, which returns later to this point.
    2. Computes the crc and sets crc_final to true
    3. If there are used modules with crc_final=false set state to ms_compiled_waitcrc and fpc returns to the scheduler, which returns later to this point.
    4. ppu is written

Loading a ppu

edit
  1. First searches the ppu file.
  2. Loads basic structure and checks source files (unless compiled with -Ur)
  3. state:=ms_load
  4. If any source file timestamp differs the module is recompiled (do_recompile:=true, is_reset:=true, state:=ms_registered, returns to scheduler, which invokes recompile_from_sources)
  5. Note that a ppu module has only a simple state (no scanner, parser, symtablestack).
  6. It loads all interface units. If there are any cycles it sets stops and returns to the scheduler. The scheduler later invokes this point again. If any crc mismatches module is marked for recompile and returned to scheduler.
  7. The interface symbols are dereferenced
  8. interface_compiled:=true
  9. It loads all implementation units. If there are any cycles it stops and returns to the scheduler. The scheduler later invokes this point again. If any crc mismatches module is marked for recompile and returned to scheduler.
  10. dereferencing implementation symbols
  11. set ppu_waitingfor_crc:=true
  12. If there are used modules with crc_final=false return to the scheduler, which returns later to this point.
  13. set ppu_waitingfor_crc:=false
  14. dereference unitimportsyms

Scheduler

edit
  1. Runs in a loop
  2. Finds unit cycles aka SCC - Strongly Connected Components.
    • Using Tarjan's algorithm starting at the main_module, following used_units edges and stopping at scc_finished=true modules.
    • the first module in a cycle is the scc_root, the others are linked by scc_next
  3. Computes scc_tree_unfinished, other_scc_unfinished, and scc_tree_crc_wait:
    • scc_tree_unfinished: current cycle or any sub cycle contains an unfinished module (not state in [ms_compiled,ms_processed])
    • other_scc_unfinished: any sub cycle contains an unfinished module
    • scc_tree_crc_wait: an unfinished module this module is waiting for
  4. Finds an unfinished leaf cycle -> current scc_root
    • all sub cycles are finished
    • the cycle contains at least one unfinished module
  5. If the cycle contains any module marked for recompile, recompile them and next loop
  6. If any module crc mismatches, recompile them and next loop
  7. If any module can continue, continue that
  8. Otherwise there is a cycle:
    • Handle reload-cycle: If there are only reloads and all reloads just waits for reloads, reload them and next loop
    • Breaking simple cycle: If there is a pas module waiting for a ppu file waiting for the pas file, recompile the ppu, next loop
    • Otherwise: recompile all do_reloads and ppu files of the cycle

Recompile

edit

An unit Foo can be marked for recompile for various reasons:

  • ppu missing
  • source file timestamp changed
  • crc mismatches
  • a used unit Bar was recompiled, and Foo may have referenced it (e.g. Bar was used in interface and Foo.interface_compiled=true), and Bar uses (indirectly) Foo.

A recompile does:

  • disconnect used units
  • reset
  • flag dependent modules (set do_reload to modules that may have references, recursively)

Open issues

edit
  • False positives:
    • The interface_crc, indirect_crc, and crc are blunt tools, creating False Positives. Gladfully interface_crc and crc affect only directly depending modules.
  • False negatives:
    • -Ur ignores the crc, so changes of generics and inline implementations do not trigger a recompile for modules compiled with -Ur. Remedy: simple: search for EnableUrCRC
    • changes to generics don't trigger recompiles in distant specializations. For example a specialization of a generic method which is not in the uses section of the specialization. Remedy: Add the unit of the generic to the used_unit list with some extra flag to skip adding symtable.
    • the indirect_crc contains only the objects. For example changing a parameter type from boolean to longint might end up with the same symbol index for the imported symbol of boolean/longint, but that lies outside the object, and thus does not contribute to the indirect_crc.
    • the crc contains the generics and inline code, but not the local symbols.
  • Some circular unit dead locks can be solved by recompiling one or a few units, instead of recompiling big parts of the cycle.
    • Probably related problem: a recompile clears the used_units and crc. Technically a recompile can result in a different list of used_units, but that is very seldom. So keeping the information might help the heuristic to find a minimal set of recompiles.