A partial evaluator, given a program and a known static part of its input data, outputs a residual program in which computations depending only on the static data have been precomputed [3]. The ideal is a black box which discovers and performs nontrivial static computations whenever possible, and never fails to terminate. Practical partial evaluators fall short of this goal: they sometimes loop (typical of functional programing partial evaluation), or terminate but are excessively conservative (typical in partial deduction 1). This paper presents efficient algorithms (being implemented) for binding-time analysis for off-line specialisers. They ensure that the specialiser performs many nontrivial static computations, and are at the same time guaranteed to terminate.