GraphImplementationOptions

The building of source code into a final product is a directed acyclic graph of transformations. However that graph need not be implemented, it may be implied.

In this document I walk through the process of building the CompiletimeDependency test case using a number of possible implementations.

The graph changes depending on the presence of the BEEF environment variable. With the BEEF macro unset the graph looks like this:

looper: looper.o
looper.o: looper.c
looper.c: bisto.h

hillfort: hillfort.o
hilfort.o: hillfort.F90
hillfort.mod: hillfort.F90

With it present the graph looks like this:

looper: looper.o
looper.o: looper.c
looper.c: oxo.h

hillfort: hillfort.o support.o
hilfort.o: hillfort.F90
hillfort.mod: hillfort.F90
hillfort.F90: support.mod
support.o: support.f90
support.mod: support.f90

Reified Graph

We may implement the graph explicitly. This process starts by examining every source file in order to build the graph. Then the graph must be trimmed to remove any nodes without edges linking them to other nodes. Finally the graph may be traverssed from initial to final nodes.

Without BEEF

• bisto.h - Ignore header file, it will be handled by preprocessing
• hillfort.F90 - Preprocess - resolve ifdef - Contains program - Create end product, linker and compile nodes
• looper.c - Preprocess - resolves ifdef and dependency on header - Contains function main - Create end product, linker and compile nodes
• oxo.h - Ignor header file, it will be handled by preprocessing
• support.f90 - Contains module - Create compile node
• Trim graph - "support.f90" node removed due to lacking edges
• Run graph from initial nodes

With BEEF

• bisto.h - Ignore header file, it will be handled by preprocessing
• hillfort.F90 - Preprocess - resolve ifdef - Contains program - Create end product, linker and compile nodes - Uses support_mod - create empty prerequisite node
• looper.c - Preprocess - resolves ifdef and dependency on header - Contains function main - Create end product, linker and compile nodes
• oxo.h - Ignor header file, it will be handled by preprocessing
• support.f90 - Contains module - populate previously created node
• Trim graph - no effect
• Run graph from initial nodes

Implicit Graph, Queue Implementation

An alternative approach is to implement the process using a queue. Here the graph is implicit. This approach is most easily thought of as a threaded consumer/producer model. It needn't be implemented this way.

As can be seen in the example "without BEEF" there is a problem with excluding unecessary stages. At the time of scanning the files it is not known which depends on which. If we wait until all files are scanned then we know but for performance reasons we would prefer to start processessing as soon as there is work to do.

Without BEEF

Producer

• bisto.h - Ignore header file, it will be handled by preprocessing
• hillfort.F90 - Add preprocess task to head of queue
• looper.c - Add preprocess task to head of queue
• oxo.h - Ignore header file, it will be handled by preprocessing
• support.f90 - No prerequisites - add compile task to head of queue

Consumer

• Compile support.f90 - No prerequisites - performed
• Preprocess looper.c - Preprocess file and add compile task to head of queue
• Compile looper.i - No prerequisites - perform compile - Contains main() - and add link task to head of queue
• Link looper - prerequisites (looper.o) met - perform
• Preprocess hillfort.F90 - Contains program - add compile tasks to head of queue
• Compile hillfort.f90 - No prerequisites - perform compile - Contains program - add link task to head of queue
• Link hillfort - Prerequisites (hillfort.o) met - perform

With BEEF

Producer

• bisto.h - Ignore header file, it will be handled by preprocessing
• hillfort.F90 - Add preprocess task to head of queue
• looper.c - Add preprocess task to head of queue
• oxo.h - Ignore header file, it will be handled by preprocessing
• support.f90 - No prerequisites - add compile task to head of queue

Consumer

• Compile support.f90 - No prerequisites - performed
• Preprocess looper.c - Preprocess file and add compile task to head of queue
• Compile looper.i - No prerequisites - perform - Contains main() - and add link task to head of queue
• Link looper - prerequisites (looper.o) met - perform
• Preprocess hillfort.F90 - Preprocess file and add compile task to head of queue
• Compile hillfort.f90 - Prerequisites (support.mod) met - perform - Contains program - add link task to head of queue
• Link hillfort - Prerequisites (hillfort.o, support.o) met - perform