Should you ever need to do dependency checking, just use Graph.pm instead of trying to do it yourself.
In my case, App::SimpleScan had a serious pessimization that I knew about: if you defined a variable, App::SimpleScan would try every possible value for it when subsituting, even if said variable did not appear in the test spec. This was because I needed to be able to have variable substitutions possibly contain other variable substitutions (though I drew the line at recursive definitions).
If you don't have some means of tracking dependencies, you must always check every possible combination of values. If you get a bunch of variables, this slows things WAY down, even if most of them only have a couple of different values, because you now have to check the cross-product of all possible values. Not good.
Graph.pm just makes all this go away. You add each variable as a node, with edges pointing to variables that this one might need to substitute. If you've defined all your variables right (i.e., no circular dependencies), then you've got what's called a directed acyclic graph (or DAG). It's essentially a forest of trees that may or may not share some nodes.
To figure out what all variables are dependent on a given one, you put the one(s) you're interested in an array, and then iterate over that, recording all the adjacent nodes. Repeat until you get no more new nodes (this could be optimized too, by pulling out nodes that have no successors, but this is fast enough for now). Ta-da: these, and only these, need to be substituted.
Oh, and Graph.pm detects cycles for you as well, so you just need to check whether any cycles got created as each variable is defined. Sweet.