Optimize Compiler for simple Reverse Polish Notation Programming Language
Wolfram Language (Mathematica), 733 728 690 564 516 506 513 548 bytes

j=Integer;f=Flatten;s=SequenceReplace;A=FixedPoint[f@s[#,{{x_j,p,y_j,t}-&gt;{y,t,x*y,p},{x_j,y_j,p}-&gt;x+y,{x_j,y_j,t}-&gt;x*y,{x_j,p,y_j,p}-&gt;{x+y,p},{x_j,t,y_j,t}-&gt;{x*y,t},{0,p}|{1,t}-&gt;{},{0,t}-&gt;{d,0}}]//.{a___,Except[i|o]}-&gt;{a}&amp;,#]&amp;;B=Expand@Check[f@FoldPairList[f/@Switch[#2,i,{{i},{#,i@c++}},o,{{Last@#},#},d,{{},Most@#},p,{{},{#[[;;-3]],Tr@#[[-2;;]]}},t,{{},{#[[;;-3]],#[[-2]]*Last@#}},_,{{},{##}}]&amp;,c=0;{},#],x]&amp;;F=MinimalBy[w=A@f[#/.m-&gt;{-1,t,p}];z=B@w;s[#,{-1,t,p}-&gt;m]&amp;/@A/@Select[Permutations@Join[w,Cases[z /.i@_-&gt;i,_j,∞]],B@#==z&amp;],Length][[1]]&amp;


Try it online!

This is a four-step tour-de-force that (1) replaces "-" with "-1 * +" so that we don't have to deal with subtractions, (2) simplifies the list of commands a bit, (3) makes a list of all permutations of this list of commands and picks out those that give the same result when parsed (executed), and (4) simplifies these lists of commands a bit and picks the shortest, after converting certain operations back to subtractions.

This code is terribly inefficient because it goes through the list of all permutations of the input code. For long input codes I don't recommend running this code; but as I read it there are no runtime or memory restrictions in this challenge.

This code does the optimization step after converting all "-" operations to "+" operations with signs flipped, and only at the end re-introduces the "-" operator when converting code back to strings. This implies for example that "i -1 i * + o" is correctly optimized to "i i - o".

As the i/o format requirement is quite loose, this code takes and returns code as lists, where the symbols "+", "-", "*" are represented by p, m, t, tokens respectively. The conversion from and to strings is done in the wrapper function given on TIO:

G[S_] := StringReplace[{"p" -&gt; "+", "m" -&gt; "-", "t" -&gt; "*"}]@StringRiffle@
         Quiet@F@
         ToExpression[StringSplit[S] /. {"+" -&gt; p, "-" -&gt; m, "*" -&gt; t}]


Un-golfed version, including the string-format wrapper and minimizing the final code string length instead of the number of tokens, and including a few more transformation niceties:

(* convert code string to list of operators *)
inputfilter[s_] := ToExpression[Flatten[StringSplit[s] /.
  {"i" -&gt; i, "o" -&gt; o, "d" -&gt; d, "+" -&gt; p, "-" -&gt; {-1, t, p}, "*" -&gt; t}]]

(* convert list of operators to code string *)
outputfilter[s_] := StringReplace[StringRiffle@Flatten@SequenceReplace[s,
  {{-1, t, p} -&gt; m,                         (* convert "-1 t p" back to "-"             *)
   {x_ /; x &lt; 0, p} -&gt; {-x, m},             (* convert "y x +" to "y -x -" when x&lt;0     *)
   {x_ /; x &lt; 0, t, p} -&gt; {-x, t, m}}],     (* convert "y x * +" to "y -x * -" when x&lt;0 *)
  {"m" -&gt; "-", "p" -&gt; "+", "t" -&gt; "*"}]     (* backsubstitution of symbols              *)

(* simplify a list of operators somewhat *)
simplifier[s_] := FixedPoint[Flatten@SequenceReplace[#,
  {{x_Integer, p, y_Integer, t} -&gt; {y, t, x*y, p},  (*  "x + y *" -&gt; "y * (xy) +"       *)
   {x_Integer, y_Integer, p} -&gt; x + y,              (*  "x y +" -&gt; "(x+y)"              *)
   {x_Integer, y_Integer, t} -&gt; x*y,                (*  "x y *" -&gt; "(xy)"               *)
   {x_Integer, p, y_Integer, p} -&gt; {x + y, p},      (*  "x + y +" -&gt; "(x+y) +"          *)
   {x_Integer, t, y_Integer, t} -&gt; {x*y, t},        (*  "x * y *" -&gt; "(xy) *            *)
   {0, p} | {1, t} -&gt; {},                           (*  "0 +" and "1 *" are deleted     *)
   {x_Integer, i, p} -&gt; {i, x, p},                  (*  "x i +" -&gt; "i x +"              *)
   {x_Integer, i, t} -&gt; {i, x, t},                  (*  "x i *" -&gt; "i x *"              *)
   {0, t} -&gt; {d, 0}}] //.                           (*  "0 *" -&gt; "d 0"                  *)
  {a___, Except[i | o]} -&gt; {a} &amp;, s]                (* delete trailing useless code     *)

(* execute a list of operators and return the list of generated outputs *)
parse[s_] := Expand@Quiet@Check[Flatten@FoldPairList[  (* stack faults are caught here     *)
  Function[{stack, command},                        (* function called for every command*)
    Flatten /@ Switch[command,                      (* code interpretation:             *)
    i, {{i}, {stack, i[inputcounter++]}},           (* output "i" and add input to stack*)
    o, {{stack[[-1]]}, stack},                      (* output top of stack              *)
    d, {{}, Most[stack]},                           (* delete top of stack              *)
    p, {{}, {stack[[;; -3]], stack[[-2]] + stack[[-1]]}},  (* add two stack elements    *)
    t, {{}, {stack[[;; -3]], stack[[-2]]*stack[[-1]]}},    (* multiply two stack elements*)
    _, {{}, {stack, command}}]],                    (* put number onto stack            *)
    inputcounter = 0; {},                           (* start with zero input counter and empty stack*)
    s],                                             (* loop over code list              *)
  x]                                                (* return "x" if an error occurred  *)

(* the main function that takes a code string and returns an optimized code string *)
F[s_] := Module[{w, q},
  w = simplifier@inputfilter@s;      (* convert input to useful form *)
  q = parse[w];                      (* execute input code *)
  MinimalBy[
    outputfilter@*simplifier /@      (* simplify and stringify selected codes          *)
      Select[Permutations[w],        (* all permutations of code list                  *)
             parse[#] == q &amp;],       (* select only those that give the correct output *)
    StringLength] // Union]          (* pick shortest solution by length               *)


Thanks to @redundancy for catching a bug: The parser needs a Expand applied to the output in order to handle distributive equivalence. 506→513

update

Now also optimizes 1 o 1 + o to 1 o 2 o. This was a surprisingly difficult case and made the code much slower. 513→548