Common parse tree for several formulas
This is the circuit minimization / logic optimization problem.   You have a circuit with some number of inputs (one per predicate p1, .., pn; or based on the representation of x)  and ~ 1k outputs (one per formula f1, .., fm).  Now the goal is to construct another equivalent circuit that computes the same output, as efficiently as possible.  That's a circuit minimization problem.  The problem is hard in general, but there are some heuristics and tools that may be effective in many situations (e.g., Espresso, Quine-McClusky, BDDs, and more).  I suggest reading about that subject and trying out one of those tools or techniques.