As to the question of how to convert a function performed iteratively using irreversible gates to the same function performed iteratively using reversible gates, you should probably accept that any boolean function from $\{0,1\}^n$ to $\{0,1\}$ can be written in $\mathsf{3CNF}$-normal form with a polynomial number of $\mathsf{AND, OR, NOT}$ gates (i.e. $\lor$, $\land$, and $\lnot$ gates). Of these three, only $\lnot$ is reversible; the other two, $\land$ and $\lor$ are not.
You should probably also accept that you can convert any function written in $\mathsf{3CNF}$ having $\{\lnot,\lor,\land\}$ gates to the same function written with a polynomial number of clauses using only $\uparrow$, the Sheffer stroke (for $\mathsf{NAND}$). The Sheffer stroke $\uparrow$ is not reversible.
It would suffice to replace the Sheffer stroke $\{\uparrow\}$, or the $\mathsf{3CNF}$ gates $\{\lor,\land,\lnot\}$, with some reversible gates.
Enter the Toffoli gate, aka the $\mathsf{CCNOT}$ gate.
Quoting from Wikipedia:
[The Toffoli gate] preserves two of its inputs a,b and replaces the third c by $c\oplus (a\cdot b)$. With $c=0$, this gives the $\mathsf{AND}$ function, and with $a\cdot b=1$ this gives the $\mathsf{NOT}$ function. Thus, the Toffoli gate is universal and can implement any reversible boolean function (given enough zero-initialized ancillary bits).
Thus, you can implement $\mathsf{AND}$ and $\mathsf{NOT}$ with Toffoli gates, and hence implement $\mathsf{NAND}$ with two Toffoli gates. The implication is that the "enough zero-initialized ancillary bits" is not more than polynomial in $n$.
I don't expect that real synthesis of boolean functions uses only Toffoli gates - but at least there's an outline of how you could convert a function written in $\mathsf{3CNF}$-normal form into some other normal form using nothing but Toffoli gates.