@ file : Suppress (" FunctionName ") Ċ Ċ package Ġedu . kit . compiler . optimization Ċ Ċ import Ġedu . kit . compiler . utils . Match Pattern Ċ import Ġedu . kit . compiler . utils . Replacement Builder Scope Ċ import Ġedu . kit . compiler . utils . Value Holder Ċ import Ġedu . kit . compiler . utils . rule Ċ import Ġfirm . Back Edges Ċ import Ġfirm . Graph Ċ import Ġfirm . Mode Ċ import Ġfirm . nodes . Add Ċ import Ġfirm . nodes . Bin op Ċ import Ġfirm . nodes . Div Ċ import Ġfirm . nodes . Minus Ċ import Ġfirm . nodes . Mod Ċ import Ġfirm . nodes . Mul Ċ import Ġfirm . nodes . Not Ċ import Ġfirm . nodes . Sub Ċ import Ġkotlin . reflect . K Class Ċ import Ġfirm . nodes . Const Ġas ĠF irm Const Ċ import Ġfirm . nodes . Node Ġas ĠF irm Node Ċ Ċ val ĠArithmetic Optimization Ġ= ĠOptimization (" ar ithmetic Ġoptimization ", Ġ:: apply Arithmetic Optimization ) Ċ Ċ private Ġfun Ġapply Arithmetic Optimization ( graph : ĠGraph ): ĠBoolean Ġ{ ĊĠĠĠ Ġvar Ġhas Changed Ġ= Ġfalse ĊĊĠĠĠ ĠBack Edges . enable ( graph ) ĊĊĠĠĠ Ġgraph . walk Top ological ( object Ġ: ĠF irm Node Visitor Adapter () Ġ{ ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġdefault Visit ( node : ĠF irm Node ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrules . forEach Ġ{ Ġrule Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . block Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode Ġis Ġa ĠBlock Ġ-> Ġir relevant Ġfor Ġarithmetic Ġoptimization ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn @ forEach ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġreplacement Ġ= Ġwith ( Replacement Scope ( graph , Ġnode . block )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrule . match ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( replacement Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ( replacement ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠRe placement . Node Ġ-> ĠGraph . exchange ( node , Ġreplacement . node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠRe placement . Node With Mem Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠBack Edges . get Out s ( node ). forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( it . node . mode Ġ== ĠMode . getM ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠGraph . exchange ( it . node , Ġreplacement . mem ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠGraph . exchange ( it . node , Ġreplacement . node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhas Changed Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ// Ġdo Ġnot Ġcheck Ġother Ġrules ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}) ĊĊĠĠĠ ĠBack Edges . disable ( graph ) ĊĊĠĠĠ Ġreturn Ġhas Changed Ċ } Ċ Ċ private Ġsealed Ġclass ĠRe placement Ġ{ ĊĠĠĠ Ġclass ĠNode ( val Ġnode : ĠF irm Node ) Ġ: ĠRe placement () ĊĠĠĠ Ġclass ĠNode With Mem ( ĊĠĠĠĠĠĠĠ Ġval Ġnode : ĠF irm Node , ĊĠĠĠĠĠĠĠ Ġval Ġmem : ĠF irm Node , ĊĠĠĠ Ġ) Ġ: ĠRe placement () Ċ } Ċ Ċ private Ġclass ĠRe placement Scope ( val Ġgraph : ĠGraph , Ġval Ġblock : ĠF irm Node ) Ġ: ĠRe placement Builder Scope Ġ{ ĊĠĠĠ Ġfun Ġnode ( node : ĠF irm Node ) Ġ= ĠRe placement . Node ( node ) ĊĠĠĠ Ġfun Ġnode With Mem ( node : ĠF irm Node , Ġmem : ĠF irm Node ) Ġ= ĠRe placement . Node With Mem ( node , Ġmem ) Ċ } Ċ Ċ private Ġsealed Ġclass ĠNode Pattern Ġ: ĠMatch Pattern < F irm Node > Ċ Ċ private Ġobject ĠAny Node Ġ: ĠNode Pattern () Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġmatches ( target : ĠF irm Node ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} Ċ } Ċ Ċ private Ġclass ĠConst ( private Ġval Ġvalue : ĠValue Holder < Int >? Ġ= Ġnull ) Ġ: ĠNode Pattern () Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġmatches ( target : Ġfirm . nodes . Node ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( target Ġ! is ĠF irm Const ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġif Ġ( target . mode Ġ!= ĠMode . getIs ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( value ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnull Ġ-> Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠValue Holder . Variable Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalue . set ( target . tar val . as Int ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠValue Holder . Constant Ġ-> Ġtarget . tar val . as Int () Ġ== Ġvalue . get () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ private Ġclass ĠInternal Binary Op < C Ġ: ĠF irm Node >( ĊĠĠĠ Ġprivate Ġval Ġleft : ĠNode Pattern , ĊĠĠĠ Ġprivate Ġval Ġright : ĠNode Pattern , ĊĠĠĠ Ġprivate Ġval Ġtype : ĠK Class < C >, Ċ ) Ġ: ĠNode Pattern () Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġmatches ( target : ĠF irm Node ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( target :: class Ġ!= Ġtype ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġwhen Ġ( target ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠBin op Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmatches In Order Ġ= Ġleft . matches ( target . left ) Ġ&& Ġright . matches ( target . right ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( matches In Order ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( target . is Com mut ative ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleft . matches ( target . right ) Ġ&& Ġright . matches ( target . left ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠDiv Ġ-> Ġreturn Ġleft . matches ( target . left ) Ġ&& Ġright . matches ( target . right ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠMod Ġ-> Ġreturn Ġleft . matches ( target . left ) Ġ&& Ġright . matches ( target . right ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġerror (" unknown Ġbin op : Ġ${ target :: class . simple Name }") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ private Ġinline Ġfun Ġ< re ified ĠC Ġ: ĠF irm Node > ĠBinary Op ( left : ĠNode Pattern , Ġright : ĠNode Pattern ) Ġ= ĊĠĠĠ ĠInternal Binary Op ( left , Ġright , ĠC :: class ) Ċ Ċ private Ġval ĠF irm Node . is Com mut ative : ĠBoolean ĊĠĠĠ Ġget () Ġ= Ġwhen Ġ( this ) Ġ{ ĊĠĠĠĠĠĠĠ Ġis ĠAdd , Ġis ĠMul Ġ-> Ġtrue ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġfalse ĊĠĠĠ Ġ} Ċ Ċ private Ġclass ĠInternal Unary Op < C Ġ: ĠF irm Node >( ĊĠĠĠ Ġprivate Ġval Ġoperand : ĠNode Pattern , ĊĠĠĠ Ġprivate Ġval Ġtype : ĠK Class < C >, Ċ ) Ġ: ĠNode Pattern () Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġmatches ( target : ĠF irm Node ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( target :: class Ġ!= Ġtype ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( target ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠMin us Ġ-> Ġoperand . matches ( target . op ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠNot Ġ-> Ġoperand . matches ( target . op ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġerror (" unknown Ġunary Ġop : Ġ${ target :: class . simple Name }") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ private Ġinline Ġfun Ġ< re ified ĠC Ġ: ĠF irm Node > ĠUnary Op ( operand : ĠNode Pattern ) Ġ= ĊĠĠĠ ĠInternal Unary Op ( operand , ĠC :: class ) Ċ Ċ // Ġutilities Ċ Ċ private Ġclass ĠOne Of ( private Ġval Ġoptions : ĠArray < out ĠNode Pattern >) Ġ: ĠNode Pattern () Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġmatches ( target : Ġfirm . nodes . Node ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġoptions . any Ġ{ Ġit . matches ( target ) Ġ} ĊĠĠĠ Ġ} Ċ } Ċ private Ġfun ĠOne Of ( var arg Ġoptions : ĠNode Pattern ) Ġ= ĠOne Of ( options ) Ċ Ċ private Ġclass ĠCondition ( private Ġval Ġchild : ĠNode Pattern , Ġprivate Ġval Ġcondition : Ġ() Ġ-> ĠBoolean ) Ġ: ĠNode Pattern () Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġmatches ( target : Ġfirm . nodes . Node ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġchild . matches ( target ) Ġ&& Ġcondition () ĊĠĠĠ Ġ} Ċ } Ċ Ċ private Ġclass ĠSave Node To ( private Ġval Ġstorage : ĠValue Holder . Variable < F irm Node >, Ġchild Fn : Ġ() Ġ-> ĠNode Pattern ) Ġ: ĠNode Pattern () Ġ{ ĊĠĠĠ Ġprivate Ġval Ġchild Ġby Ġlazy Ġ{ Ġchild Fn () Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġmatches ( target : ĠF irm Node ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġstorage . set ( target ) ĊĠĠĠĠĠĠĠ Ġreturn Ġchild . matches ( target ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ private Ġfun ĠSave Any Node To ( storage : ĠValue Holder . Variable < F irm Node >) Ġ= ĠSave Node To ( storage ) Ġ{ ĠAny Node Ġ} Ċ Ċ @ Suppress (" FunctionName ") Ċ private Ġfun ĠSave Const To ( storage : ĠValue Holder . Variable < F irm Node >) Ġ= ĠSave Node To ( storage ) Ġ{ ĠConst () Ġ} Ċ Ċ @ Suppress (" FunctionName ") Ċ private Ġfun ĠSave Non Const To ( value : ĠValue Holder . Variable < F irm Node >) Ġ= ĊĠĠĠ ĠCondition ( Save Any Node To ( value )) Ġ{ Ġvalue . get () Ġ! is ĠF irm Const Ġ} Ċ Ċ // Ġrules Ċ Ċ private Ġval Ġrules Ġ= ĠlistOf ( ĊĊĠĠĠ Ġrule ("( any Ġ+ Ġ 0 )") Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġany Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠĠĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Add >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( any ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠConst ( constant ( 0 )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode ( any . get ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}, ĊĠĠĠ Ġrule ("( any Ġ+ Ġ(- sub tr ah end ))) ") Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġany Ġ= Ġvariable < F irm Node >() ĊĠĠĠĠĠĠĠ Ġval Ġsub tr ah end Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠĠĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Add >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( any ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠUnary Op < Minus >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( sub tr ah end ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph . new Sub ( block , Ġany . get (), Ġsub tr ah end . get ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}, ĊĊĠĠĠ Ġrule ("( any Ġ- Ġ 0 )") Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġany Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠĠĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Sub >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( any ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠConst ( constant ( 0 )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode ( any . get ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}, ĊĠĠĠ Ġrule ("( 0 Ġ- Ġany )") Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġany Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠĠĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Sub >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠConst ( constant ( 0 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( any ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode ( graph . new Minus ( block , Ġany . get ())) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}, ĊĠĠĠ Ġrule ("( any Ġ- Ġany )") Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsub Ġ= Ġvariable < F irm Node >() ĊĠĠĠĠĠĠĠ Ġval Ġleft Ġ= Ġvariable < F irm Node >() ĊĠĠĠĠĠĠĠ Ġval Ġright Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠĠĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠSave Node To ( sub ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Sub >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( left ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( right ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġcondition Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft . get () Ġ== Ġright . get () ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode ( graph . new Const ( 0 , Ġsub . get (). mode )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}, ĊĊĠĠĠ Ġrule ("( any Ġ* Ġ 1 )") Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġany Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠĠĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Mul >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( any ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠConst ( constant ( 1 )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode ( any . get ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}, ĊĠĠĠ Ġrule ("( any Ġ* Ġ 0 )") Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġzero Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠĠĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Mul >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠAny Node , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Node To ( zero ) Ġ{ ĠConst ( constant ( 0 )) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode ( zero . get ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}, ĊĠĠĠ Ġrule ("( any Ġ* Ġ- 1 )") Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġany Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠĠĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Mul >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( any ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠConst ( constant (- 1 )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode ( graph . new Minus ( block , Ġany . get ())) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}, ĊĊĠĠĠ Ġrule ("( any Ġ/ Ġ 1 )") Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdiv Ġ= Ġvariable < F irm Node >() ĊĠĠĠĠĠĠĠ Ġval Ġany Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠĠĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠSave Node To ( div ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Div >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( any ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠConst ( constant ( 1 )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode With Mem ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġany . get (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( div . get () Ġas ĠDiv ). mem ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}, ĊĠĠĠ Ġrule ("( any Ġ/ Ġ- 1 )") Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdiv Ġ= Ġvariable < F irm Node >() ĊĠĠĠĠĠĠĠ Ġval Ġany Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠĠĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠSave Node To ( div ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Div >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( any ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠConst ( constant (- 1 )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode With Mem ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph . new Minus ( block , Ġany . get ()), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( div . get () Ġas ĠDiv ). mem ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}, ĊĊĠĠĠ Ġrule ("( any Ġ% Ġ 1 ) Ġor Ġ( any Ġ% Ġ- 1 )") Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmod Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠĠĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠSave Node To ( mod ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Mod >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠAny Node , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠOne Of ( Const ( constant ( 1 )), ĠConst ( constant (- 1 ))) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmod Node Ġ= Ġmod . get () Ġas ĠMod ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode With Mem ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph . new Const ( 0 , Ġmod Node . res mode ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmod Node . mem ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ}, ĊĊĠĠĠ Ġ// ĠMove Ġconstants Ġas Ġfar Ġout Ġas Ġpossible Ġto Ġallow Ġconstant Ġfold ing Ġto Ġcombine Ġthem Ġif Ġin Ġa Ġchain Ġof Ġoperations . ĊĠĠĠ Ġmove Constant Out wards Rule < Add >(" ( any Ġ+ Ġconst ) Ġ+ Ġnon Const Ġ-> Ġ( any Ġ+ Ġnon Const ) Ġ+ Ġconst ", ĠGraph :: new Add ), ĊĠĠĠ Ġgroup Constants Rule < Add >(" ( any Ġ+ Ġinner Const ) Ġ+ Ġouter Const Ġ-> Ġany Ġ+ Ġ( inner Const Ġ+ Ġouter Const )", ĠGraph :: new Add , ĠGraph :: new Add ), ĊĊĠĠĠ Ġmove Constant Out wards Rule < Mul >(" ( any Ġ* Ġconst ) Ġ* Ġnon Const Ġ-> Ġ( any Ġ* Ġnon Const ) Ġ* Ġconst ", ĠGraph :: new Mul ), ĊĠĠĠ Ġgroup Constants Rule < Mul >(" ( any Ġ* Ġinner Const ) Ġ* Ġouter Const Ġ-> Ġany Ġ* Ġ( inner Const Ġ* Ġouter Const )", ĠGraph :: new Mul , ĠGraph :: new Mul ), ĊĊĠĠĠ Ġmove Constant Out wards Rule < Sub >(" ( any Ġ- Ġconst ) Ġ- Ġnon Const Ġ-> Ġ( any Ġ- Ġnon Const ) Ġ- Ġconst ", ĠGraph :: new Sub ), ĊĠĠĠ Ġgroup Constants Rule < Sub >(" ( any Ġ- Ġinner Const ) Ġ- Ġouter Const Ġ-> Ġany Ġ- Ġ( inner Const Ġ+ Ġouter Const )", ĠGraph :: new Sub , ĠGraph :: new Add ), ĊĊĠĠĠ Ġ// Ġdistribut ive ĊĠĠĠ Ġdistribut ive Rule < Add >(" ( any Ġ* Ġleft ) Ġ+ Ġ( any Ġ* Ġright ) Ġ-> Ġany Ġ* Ġ( left Ġ+ Ġright )", ĠGraph :: new Add ), ĊĠĠĠ Ġdistribut ive Rule < Sub >(" ( any Ġ* Ġleft ) Ġ- Ġ( any Ġ* Ġright ) Ġ-> Ġany Ġ* Ġ( left Ġ- Ġright )", ĠGraph :: new Sub ), Ċ ) Ċ Ċ // Ġ( any Ġ+ Ġconst ) Ġ+ Ġnon Const Ġ-> Ġ( any Ġ+ Ġnon Const ) Ġ+ Ġconst Ċ private Ġinline Ġfun Ġ< re ified ĠNode Type Ġ: ĠF irm Node > Ġmove Constant Out wards Rule ( ĊĠĠĠ Ġname : ĠString , ĊĠĠĠ Ġcross inline ĠnewNode : ĠGraph .( F irm Node , ĠF irm Node , ĠF irm Node ) Ġ-> ĠF irm Node , Ċ ) Ġ= Ġrule < F irm Node , ĠRe placement , ĠRe placement Scope >( name ) Ġ{ ĊĠĠĠ Ġval Ġany Ġ= Ġvariable < F irm Node >() ĊĠĠĠ Ġval Ġconst Ġ= Ġvariable < F irm Node >() ĊĠĠĠ Ġval Ġnon Const Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠ ĠBinary Op < NodeType >( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < NodeType >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( any ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Const To ( const ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠSave Non Const To ( non Const ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) ĊĊĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠ Ġnode ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgraph . new Node ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġblock , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph . new Node ( block , Ġany . get (), Ġnon Const . get ()), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġconst . get () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ // Ġ( any Ġ+ Ġinner Const ) Ġ+ Ġouter Const Ġ-> Ġany Ġ+ Ġ( inner Const Ġ+ Ġouter Const ) Ċ private Ġinline Ġfun Ġ< re ified ĠNode Type Ġ: ĠF irm Node > Ġgroup Constants Rule ( ĊĠĠĠ Ġname : ĠString , ĊĠĠĠ Ġcross inline Ġnew Outer Node : ĠGraph .( F irm Node , ĠF irm Node , ĠF irm Node ) Ġ-> ĠF irm Node , ĊĠĠĠ Ġcross inline Ġnew Inner Node : ĠGraph .( F irm Node , ĠF irm Node , ĠF irm Node ) Ġ-> ĠF irm Node , Ċ ) Ġ= Ġrule < F irm Node , ĠRe placement , ĠRe placement Scope >( name ) Ġ{ ĊĠĠĠ Ġval Ġany Ġ= Ġvariable < F irm Node >() ĊĠĠĠ Ġval Ġinner Const Ġ= Ġvariable < F irm Node >() ĊĠĠĠ Ġval Ġouter Const Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠ ĠBinary Op < NodeType >( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < NodeType >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( any ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Const To ( inner Const ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠSave Const To ( outer Const ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) ĊĊĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠ Ġnode ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgraph . new Outer Node ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġblock , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġany . get (), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph . new Inner Node ( block , Ġinner Const . get (), Ġouter Const . get ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ private Ġinline Ġfun Ġ< re ified ĠC Ġ: ĠF irm Node > Ġdistribut ive Rule ( ĊĠĠĠ Ġname : ĠString , ĊĠĠĠ Ġcross inline Ġnew Inner Node : ĠGraph .( F irm Node , ĠF irm Node , ĠF irm Node ) Ġ-> ĠF irm Node Ċ ) Ġ= Ġrule < F irm Node , ĠRe placement , ĠRe placement Scope >( name ) Ġ{ ĊĠĠĠ Ġval Ġleft First Ġ= Ġvariable < F irm Node >() ĊĠĠĠ Ġval Ġleft Second Ġ= Ġvariable < F irm Node >() ĊĠĠĠ Ġval Ġright First Ġ= Ġvariable < F irm Node >() ĊĠĠĠ Ġval Ġright Second Ġ= Ġvariable < F irm Node >() ĊĊĠĠĠ Ġmatch ( ĊĠĠĠĠĠĠĠ ĠBinary Op < C >( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Mul >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( left First ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( left Second ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBinary Op < Mul >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( right First ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSave Any Node To ( right Second ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) ĊĊĠĠĠ Ġvar Ġsame : ĠF irm Node ? Ġ= Ġnull ĊĠĠĠ Ġvar Ġother Left : ĠF irm Node ? Ġ= Ġnull ĊĠĠĠ Ġvar Ġother Right : ĠF irm Node ? Ġ= Ġnull ĊĠĠĠ Ġcondition Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn @ condition Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft First . get () Ġ== Ġright First . get () Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsame Ġ= Ġleft First . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġother Left Ġ= Ġleft Second . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġother Right Ġ= Ġright Second . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft First . get () Ġ== Ġright Second . get () Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsame Ġ= Ġleft First . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġother Left Ġ= Ġleft Second . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġother Right Ġ= Ġright First . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Second . get () Ġ== Ġright First . get () Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsame Ġ= Ġleft Second . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġother Left Ġ= Ġleft First . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġother Right Ġ= Ġright Second . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Second . get () Ġ== Ġright Second . get () Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsame Ġ= Ġleft Second . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġother Left Ġ= Ġleft First . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġother Right Ġ= Ġright First . get () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreplace With Ġ{ ĊĠĠĠĠĠĠĠ Ġnode ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgraph . new Mul ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġblock , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsame !! , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġgraph . new Inner Node ( block , Ġother Left !! , Ġother Right !! ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ} Ċ } Ċ