EDIT (Aug 22, 2011):
I am further simplifying the question and putting a bounty on the question. Perhaps this simpler question will have an easy answer. I'm also going to strikethrough all the parts of the original question that are no longer relevant. (Thanks to Stasys Jukna and Ryan O'Donnell for partially answering the original question!)
Given an AC0 circuit with depth k and size S, there exists another AC0 circuit computing the same function with depth k and size $O(S^k)$ such that the new circuit has fanout = 1 for all gates. In other words, the circuit looks like a tree (except at the inputs, since the inputs may fanout to more than one gate). One way to do this is by duplicating all the gates that have fanout > 1 until all gates have fanout = 1.
But is this the most efficient way to convert AC0 circuits to AC0 circuits with fanout 1? I read the following in Lecture 14 of Ryan O'Donnell's course notes:
Suppose C is any depth-k circuit of size S which computes Parity. It is an exercise to show that C can be converted into a leveled depth-k circuit, where the levels alternate AND and OR gates, the inputs wires are the 2n literals, and each gate has fan-out 1 (i.e., it’s a tree) — and the size increases to at most $(2kS)^2 \leq O(S^4)$.
Footnote: Actually, this is a slightly tricky exercise. It’s easier if you only have to get size $O(S^k)$, which is almost the same for our purposes if you think of k as a “constant”.
Does this mean there is a way to take any depth k AC0 circuit of size S and convert it to an AC0 circuit with fanout 1, depth k and size $(2kS)^2$? If so, how is this done and is this the best-known method?
Given an AC0 circuit with depth k and size S, what's the best-known method (in terms of minimizing the circuit size of the resultant circuit) of converting this to an AC0 circuit of depth k and gate fanout 1? Are there any lower bounds known for this?
Newer, simpler question:
This question is a relaxation of the original one where I don't insist that the resultant circuit be constant depth. As explained above, there is a way to convert an AC0 circuit with depth k, size S into a circuit with size $O(S^k)$ such that the new circuit has fanout = 1 for all gates. Is there a better construction?
Given an AC0 circuit with depth k and size S, what's the best-known method (in terms of minimizing the circuit size of the resultant circuit) of converting this to a circuit of any depth with gate fanout 1?