Safe Haskell  None 

Language  Haskell98 
This module contains the core of the classical circuit optimization algorithm.
Synopsis
 trace :: String > b > b
 moveWire :: Wire > Wire > Gate > Gate
 flipCtl :: Wire > Gate > Gate
 moveWireFlip :: Wire > Wire > Gate > Gate
 suppress_garbage :: [Gate] > IntSet > [Gate]
 suppressGarbageGates :: ([Gate], [Wire]) > ([Gate], [Wire])
 getAllWires :: [Gate] > IntSet
 getInitWires :: [Gate] > IntSet
 getInputWires :: [Gate] > IntSet
 compressWires :: [Wire] > ([Gate], [Wire]) > ([Gate], [Wire])
 type GateId = Int
 type GateIdSet = IntSet
 type UsedWire = IntMap GateIdSet
 gateIdFindMin :: GateIdSet > Maybe GateId
 gateIdFindMax :: GateIdSet > Maybe GateId
 pairUsedWire :: UsedWire > Wire > GateIdSet
 firstUsedWire :: UsedWire > Wire > Maybe GateId
 lastUsedWire :: UsedWire > Wire > GateId
 nextUsedGate :: UsedWire > GateId > GateId > Wire > GateId
 circuitControlWires :: GateId > [Gate] > UsedWire
 circuitNotWires :: GateId > [Gate] > UsedWire
 exp_length :: Exp > Int
 exp_list_and :: [Set Exp] > Set Exp
 expEvalCtl :: IntMap (Set (Exp, Int)) > (Wire, Bool) > Set Exp
 expEvalGate :: IntMap (Set (Exp, Int)) > Gate > IntMap (Set (Exp, Int))
 data ExpState = ExpState {}
 initExpState :: IntSet > [Wire] > [Gate] > ExpState
 data EvalCirc a = EvalCirc (ExpState > (ExpState, a))
 runEvalCirc :: IntSet > [Wire] > [Gate] > EvalCirc a > ExpState
 getExpState :: EvalCirc ExpState
 setExpState :: ExpState > EvalCirc ()
 newFreshVar :: EvalCirc Integer
 pullNewGate :: EvalCirc (Maybe Gate)
 changeFuture :: [Gate] > EvalCirc ()
 updateFuture :: (Gate > Gate) > EvalCirc (IntSet, IntSet)
 storeOldGate :: Gate > EvalCirc ()
 incrGateId :: EvalCirc ()
 getAllWiresInCirc :: EvalCirc IntSet
 setAllWiresInCirc :: IntSet > EvalCirc ()
 removeFromAllWiresInCirc :: Int > EvalCirc ()
 getExpMap :: EvalCirc (IntMap (Set (Exp, Int)))
 setExpMap :: IntMap (Set (Exp, Int)) > EvalCirc ()
 updateUsedControlWires :: (UsedWire > UsedWire) > EvalCirc ()
 updateUsedNotWires :: (UsedWire > UsedWire) > EvalCirc ()
 updateOutWires :: ([Wire] > [Wire]) > EvalCirc ()
 addToSkipGates :: GateId > Gate > EvalCirc ()
 sendEndOfTime :: Gate > EvalCirc ()
 shiftGate :: Gate > GateId > EvalCirc ()
 pairEqualExp :: IntMap [Exp] > IntMap [Exp] > [Wire] > [(Wire, Wire)]
 pruneListExp :: Int > Set (Exp, Int) > Set (Exp, Int)
 stepEvalCirc :: EvalCirc Bool
 stepSwapCirc :: EvalCirc Bool
 stepSwapCirc_simple :: EvalCirc Bool
 runWhile :: Monad m => (a > Bool) > m a > m ()
 stripNoOp :: [Gate] > [Gate]
 alg_simplify :: ([Gate], [Wire]) > ([Gate], [Wire])
 alg_swap :: ([Gate], [Wire]) > ([Gate], [Wire])
 alg_swap_simple :: ([Gate], [Wire]) > ([Gate], [Wire])
 is_equal_list :: Eq a => [a] > [a] > Int > (Int, Bool)
 get_list_init :: [Gate] > [Wire]
 simplRec' :: ([Gate], [Wire]) > ([Gate], [Wire])
 simplRec :: ([Gate], [Wire]) > ([Gate], [Wire])
Auxiliary definitions
trace :: String > b > b Source #
Internal definition of a trace, for debugging purposes. This is a noop, but can be replaced to turn on debugging.
moveWire :: Wire > Wire > Gate > Gate Source #
Change a wire ID in a gate. The first two arguments are the old and the new wire ID.
flipCtl :: Wire > Gate > Gate Source #
Flip the control on the given wire (from positive to negative or vice versa).
moveWireFlip :: Wire > Wire > Gate > Gate Source #
Change a wire ID in a gate and flip the potential control.
Small, simple optimizations
suppress_garbage :: [Gate] > IntSet > [Gate] Source #
Suppress gates acting on garbage wires, i.e., wires that are not in the input set.
suppressGarbageGates :: ([Gate], [Wire]) > ([Gate], [Wire]) Source #
Like suppress_garbage
, but packaged in a manner that is friendly for composition.
Compression of wire numbering
As the optimization process goes on, many init gates will end
up being discarded. The function compressWires
compacts the wire
numbering scheme to make a smaller circuit.
getAllWires :: [Gate] > IntSet Source #
Get the set of all wires used by the circuit.
getInitWires :: [Gate] > IntSet Source #
Get the set of wires initialized by the circuit.
getInputWires :: [Gate] > IntSet Source #
Get the set of input wires, i.e., the ones that are used but not initialized.
compressWires :: [Wire] > ([Gate], [Wire]) > ([Gate], [Wire]) Source #
Compress the wire numbering.
A useful data structure
When considering a particular point in a circuit (i.e., in a list
of gates), to decide whether a given wire is used or controlled
before or after, we keep a datastructure UsedWire
.
type UsedWire = IntMap GateIdSet Source #
A map from wires to pairs of GateId
s. The left member gives the
ID of the first gate using the wire, and the right member gives the
ID of the last gate using the wire.
firstUsedWire :: UsedWire > Wire > Maybe GateId Source #
Get the first gate using the wire in the future.
lastUsedWire :: UsedWire > Wire > GateId Source #
Get the last gate using the wire in the past. Return 0 if none.
nextUsedGate :: UsedWire > GateId > GateId > Wire > GateId Source #
nextUsedGate
ws g g' w: Look for the next gate in ws
corresponding to wire w, starting from g. Return g' if none.
circuitControlWires :: GateId > [Gate] > UsedWire Source #
For each wire, find the set of gates placing a control on it.
circuitNotWires :: GateId > [Gate] > UsedWire Source #
For each wire, find the set of gates acting on it with NOT.
Algebraic optimization method
To each wire in a circuit, we attach a set of formulas. At each
iteration, the wire that gets modified is updated with its new
value, using all the possible values, possibly together with a
fresh variable. At each iteration, we also strip away the
expressions that get too large. Here, the size of an algebraic
expression is measured by the exp_length
function.
exp_length :: Exp > Int Source #
Calculate the size of an algebraic expression.
exp_list_and :: [Set Exp] > Set Exp Source #
Given a list of sets of expressions, form the conjunction of every possible choice of one expression from each set. For example.
exp_list_and [{a,b}, {c,d}, {e,f}] = [a∧c∧e, a∧c∧f, a∧d∧e, a∧d∧f, b∧c∧e, b∧c∧f, b∧d∧e, b∧d∧f].
expEvalCtl :: IntMap (Set (Exp, Int)) > (Wire, Bool) > Set Exp Source #
Evaluate a control with respect to a state.
expEvalGate :: IntMap (Set (Exp, Int)) > Gate > IntMap (Set (Exp, Int)) Source #
Evaluate a gate with respect to a state.
State of the optimization automaton
The state of the automaton. This contains in particular the current state, the past and future gates, and a fresh variable.
ExpState  

initExpState :: IntSet > [Wire] > [Gate] > ExpState Source #
The initial state for a given set of parameters.
The state monad
The state monad corresponding to ExpState
.
Lowlevel access functions
getExpState :: EvalCirc ExpState Source #
Retrieve the state.
setExpState :: ExpState > EvalCirc () Source #
Set the state.
Higherlevel access functions
newFreshVar :: EvalCirc Integer Source #
Create a fresh variable
changeFuture :: [Gate] > EvalCirc () Source #
Modify the future gates.
updateFuture :: (Gate > Gate) > EvalCirc (IntSet, IntSet) Source #
Update the future using the given parameter function. Return two sets
of gateId
s that got modified: the first set concerns the controls,
the second set the NOT gates.
storeOldGate :: Gate > EvalCirc () Source #
Store a gate in the past.
incrGateId :: EvalCirc () Source #
Increase the '@gateId@' (i.e., go forward).
getAllWiresInCirc :: EvalCirc IntSet Source #
Get the set of all wires.
setAllWiresInCirc :: IntSet > EvalCirc () Source #
Set the set of all wires.
removeFromAllWiresInCirc :: Int > EvalCirc () Source #
Remove a gate from the set of all wires.
getExpMap :: EvalCirc (IntMap (Set (Exp, Int))) Source #
Get the algebraic representation of the set of wires.
setExpMap :: IntMap (Set (Exp, Int)) > EvalCirc () Source #
Set the algebraic representation of the state of wires.
updateUsedControlWires :: (UsedWire > UsedWire) > EvalCirc () Source #
Update the database recording the controlled wires.
updateUsedNotWires :: (UsedWire > UsedWire) > EvalCirc () Source #
Update the database recording the NOT gates.
sendEndOfTime :: Gate > EvalCirc () Source #
Send a gate to the end of the future.
Auxiliary functions
pairEqualExp :: IntMap [Exp] > IntMap [Exp] > [Wire] > [(Wire, Wire)] Source #
pairEqualExp m1 m2 ws
: returns a list of pairs of wires (x,y)
such that m2 x = m1 x = m1 y
.
pruneListExp :: Int > Set (Exp, Int) > Set (Exp, Int) Source #
From a set of expressions (annotated with sizes), prune the ones whose size is larger than n.
The algebraic optimization automaton
stepSwapCirc_simple :: EvalCirc Bool Source #
A more elementary version of
: shuffle the
circuit by sending to the end all the NOT gates that can be sent
there. Return stepSwapCirc
False
when the end of the circuit is reached,
True
otherwise.
Some wrappers
alg_simplify :: ([Gate], [Wire]) > ([Gate], [Wire]) Source #
Wrapper around stepEvalCirc
.
alg_swap_simple :: ([Gate], [Wire]) > ([Gate], [Wire]) Source #
Wrapper around stepSwapCirc_simple
.
Multipass optimization
is_equal_list :: Eq a => [a] > [a] > Int > (Int, Bool) Source #
Auxiliary function. Simultaneously compute the maximum of the lengths of two lists, and their pointwise equality.
get_list_init :: [Gate] > [Wire] Source #
Get the list of initialized wires from a circuit.
simplRec' :: ([Gate], [Wire]) > ([Gate], [Wire]) Source #
Do several passes of
until it reaches a fixed point.alg_simplify