Caching for predicate bits per state
The various <fsm/pred.h> predicates could be cached per state, as two bitfields: a set of their values, and a set of whether those values are valid (known), or invalidated (currently unknown).
Then whenever a predicate function is called, if a bit is valid, there's no need to re-do the work of finding out.
Various operations would invalidate these bits; for example something like adding an epsilon edge would invalidate the "isdfa" predicate bit for the state to which it's added, and any of the states which can indirectly reach it. That would be hard to find in general, so conservatively the epsilon-adding function could invalidate all "isdfa" predicates.
In a better case, for the "iscomplete" predicate, when adding an edge to a state, the fsm_addedge_literal() function could observe current completeness of the state being added to, and leave that predicate set if the edge is not already present. This can be done without touching other states.
The .isend field could possibly also be moved to one of the predicate bits; arguably it's a predicate, just predicated on externally-defined information.
It might also make sense to provide the same set of bits for an entire struct fsm.