Auto-tuners automate the performance tuning of parallel applications. Three major drawbacks of current approaches are 1) they mainly focus on numerical software; 2) they typically do not attempt to reduce the large search space before search algorithms are applied; 3) the means to provide an auto-tuner with additional information to improve tuning are limited. Our paper tackles these problems in a novel way by focusing on the interaction between an auto-tuner and a parallel application. In particular, we introduce Atune-IL, an instrumentation language that uses new types of code annotations to mark tuning parameters, blocks, permutation regions, and measuring points. Atune-IL allows a more accurate extraction of meta-information to help an auto-tuner prune the search space \emph{before} employing search algorithms. In addition, Atune-IL's concepts target parallel applications in general, not just numerical programs. Atune-IL has been successfully evaluated in several case studies with parallel applications differing in size, programming language, and application domain; one case study employed a large commercial application with nested parallelism. On average, Atune-IL reduced search spaces by 78\%. In two corner cases, 99\% of the search space could be pruned.