This new version of the answer tries to take into account the changes
in the question, and the information exchanged in the comments.
This answer assumes that $S$ should be the set of variables that have a
content that is used in some defined fragment of the program, rather
than, at some point in the program, the variables with a content that
will be needed before the end of the program.
For the latter, the usual term is live variables, as remarked in a comment by Klaus Draeger.
The former is a generalisation of the concept of use, as appears
in dataflow analysis, and particularly in such concepts as
Use-Define or Use-Definition chains (UD chains), as well as
Definition-Use chains (DU chains). The concept of use is usually
intended for elementary program statements such as an expression
appearing in an assignment or a function call. Recall that this
originates with analysis and optimization of old Fortran programs in
the late 1960s and in the 1970s, and the was no real concept of a
compound statement at the time in the Fortran language.
But there is no reason not to extend the concept to larger program
fragments that form a meaningful whole. Thus used variable or
used set seem to be exactly the concepts and terminology that you
are looking for.
Now, there may be a difficulty in defining what is implied in the
expression "is used by". It may just mean: "syntactically appears in",
which is as simple as you can make it. This is indeed purely
syntactic, but rather non satisfactory, because the variable may well
appear only in a statement that changes its value, rather than use the
value it already has. This is too simplistic is is clearly not what
was intended by the creators of the concept.
Then a better definition will state that the occurrence of a variable
must imply that its value is actually used. But as soon as you say
that, you are no longer in syntax since you must use some of the
meaning of the program fragment to know whether the occurrence of the
variable is for using or for changing its value (or possibly is simply
irrelevant). And when you start using the semantics of the language
construct, there is no clear limit on how much of the semantics you
The definition given in page 632 of the Dragon Book 1988 is:
We say that a variable is used at a statement $s$ if its $r$-value may be required.
First one should note the use of
if rather than
iff, which clearly
indicates that some variables not meeting the condition may end up
being qualified as used. This even reinforced by the
Then, this almost definition does not bring much light on the issue. What does it mean to
be required. Typically, if a variable is an argument to a subprogram
(procedure, function, method, ...), you may think it is required. But
if further analysis shows that the value of this argument is not
actually used in the subprogram, and the argument is only used to
return a result, the $r$-value of the variable is not required. Some
may object that this could be handled by an appropriate type system,
which they consider syntax (I do not). But the fact that a value is
not required may depend on deeper semantic analysis (such as in
example 4 of the question). Furthermore, the evolution of type systems
and type theory tends to allow inclusion in types of most thing you
may want to say or prove about a variable, which would hardly qualify
Thus the situation is that there is not really an undisputable
syntactic (?) reference definition of "used variable", and it depends
essentially on an arbitrary choice implied by the set of techniques
used to analyze the program and the level of knowledge it brings
regarding actual use of the variable value at run-time.
On the other hand it is possible to give a reference semantic
definition for a set $S$ of used variables:
A variable is used in some program fragment iff there is a computation of that program such that the results and effects
of executing that fragment depend on the value of that variable before execution.
This is not completely satisfactory, because there are other
parameters that could be considered, and might suggest a different
terminology, though not change the above remarks about syntax and
For example, in a sequential context, the above definition is clear,
and refers to the value of the variable before executing the program
(fragment). However, one may still question what is considered an
effect, what is an impact on execution. Execution time could well be
part of the semantics of a program, or not. Then, in a parallel
execution context, you would consider more than the initial value of
the variable. But I will ignore this, as the question has not been
considering it (as far as I can see), and I will stick to the
The set $S$ thus defined semantically is the most precise
(i.e. minimal) set of variables that can matter in any computation,
though some may not matter in some computation.
But this set is not necessarily computable. It is recursively
enumerable, since a Turing Machine could simulate in parallel all possible
computations, and enumerate all the variables that turn out to be used
effectively (in the sense of our definition) in some computation. But
determining that some variable will not be used in a computation is
The best we can hope for is to exhibit a superset of $S$, such that we
are sure not to miss any relevant variable. This is precisely what is
done by the various techniques that can be called upon to determine
the used variables. But they do not all produce the same result and
the results they give can be more or less precise.
If some program analysis technique $T_i$ produces a set $S_i$ of used
variable, we say that $T_i$ is correct iff $S\subseteq S_i$.
If two techniques $T_1$ and $T_2$ produce respectively the sets $S_1$
and $S_2$, then $T1$ is better, more precise than $T_2$ iff
$S\subseteq S_1\subseteq S_2$.
The only thing that has a precise definition (up to the above caveat)
is the set S, enven though possibly not computable. It is also the
reference for any other set to be considered acceptable in practice, and is the smallest, the most precise of them all.
Hence, the expressions "used set" and "used variable" should be
reserved for that set.
And I suggest that the other sets that are considered in practice,
should use the same name, qualified with the name of the technique
that produced them. If the technique is unique and unnamed, it could
be called the computed use set (what is called
SYin the question),
or just used set when there is no ambiguity.