w      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRS T U V W X Y Z [ \ ] ^ _ ` a b c d e fghijklmnopqrstuvwxyz{|}~Safe- is used to specify the number of threads in  * and +. @Every instrument must define an instance of this class for each E of its passes. It is used to tell the evaluator whether it needs to @ back-track. Instruments which do not back-track should use the 3 default implementation of backtrack which returns  (which = means that no back-tracking is necessary.) If more than one = instrument requests that the evaluator back-tracks then the D evaluator will back-track to the earliest of the requested passes. >This class is used to create the next global context when the B multi-pass algorithm proceeds to the next pass or back-tracks to  the previous pass. >This class is used to create the next thread context when the B multi-pass algorithm proceeds to the next pass or back-tracks to  the previous pass. "The type of the first argument of   . It used to $ read and write the thread context. "The type of the first argument of   . It enables  instruments to run  in the  monad. (Clearly the  st2ToMP' argument needs to be used with care.) 5This abstract datatype is used as the result type of > createInstrument. Instrument authors can create it using the  (3 function, but cannot unwrap it. This ensures that , instruments can only be constructed by the Control.Monad.MultiPass  library. GEvery instrument must define an instance of this class for each of its passes. For example, the  instrument !defines the following instances:  < instance Instrument tc () () () (Counter i r w Off Off tc)   instance Num i => F Instrument tc (CounterTC1 i r) () (Counter i r w On Off tc)   instance Num i => E Instrument tc (CounterTC2 i r) () (Counter i r w On On tc) The functional dependency from instr to tc and gc enables the )A function to automatically deduce the type of the thread context "and global context for each pass. -This class is used when multiple threads are  spawned.  is used to create a new thread ) context for each of the new threads and  is A used to merge them back together when the parallel region ends. 2 is an abstract datatype containing the prologue, 3 body, and epilogue of a multi-pass algorithm. Use  ' to construct an object of type . =This monad is used to implement the epilogue of a multi-pass  algorithm. =This monad is used to implement the prologue of a multi-pass  algorithm. 9This monad is used to implement the body of a multi-pass  algorithm. , , and  are = trivial newtype wrappers around this monad. Instruments can  construct computations in the  monad, but then use  $, %, and & to A restrict which of the three stages it is allowed to be used in. BThis datatype is used by the back-tracking mechanism. Instruments ? can request that the evaluator back-tracks to a specific pass @ number. Instruments which use back-tracking store the relevant 2 PassNumbers in their global context. The current  is  the first argument of  for this  purpose. - is an abstract datatype. Instruments should  never need to create a new  or modify an existing one, ! so no functions that operate on  are exported from this  module. This datatype is used by the  and  - classes to specify whether the algorithm is = progressing to the next pass or back-tracking to a previous @ pass. When back-tracking occurs, the current thread and global  contexts are first passed the  command. Then they are  passed the  command N times, where N is the 7 number of passes that need to be revisited. Note that N can be = zero if only the current pass needs to be revisited, so the  5 command may not be used. This is the reason why the  ! command is always issued first. ?Trivial monad which computes absolutely nothing. It is used to . switch off a pass of a multi-pass algorithm. Trivial monad, equivalent to . 5 Used to switch on a pass of a multi-pass algorithm. @The main function of a multi-pass algorithm needs to be wrapped . in a newtype so that it can be packaged with " and   .. The newtype needs to be made an instance of  ! so that it can unwrapped by the  implementation. Used in conjunction with " to build a Peano number ( corresponding to the number of passes. "*This datatype is used in conjunction with   to package the B main function of the multi-pass algorithm. For an example of how * they are used, see the implementation of   or any of the * other examples in the Example directory. $BRestrict a computation so that it can only be executed during the 7 body of the algorithm (not the prologue or epilogue). %BRestrict a computation so that it can only be executed during the  prologue. &BRestrict a computation so that it can only be executed during the  epilogue. '9Combine the prologue, body, and epilogue of a multi-pass  algorithm to create the  object which is required by  the ) function. (Create an object of type  . It is needed when  defining a new instance of the   class. )9This function is used to run a multi-pass algorithm. Its 8 complicated type is mostly an artifact of the internal B implementation, which uses type classes to generate the code for E each pass of the algorithm. Therefore, the recommended way to learn  how to use )+ is to look at some of the examples in the  Example sub-directory. *Use m threads to run n instances of the function f. The , results are returned in an array of length n. +Modified version of *" which discards the result of the / function, rather than writing it to an array. ,=Read-only ST2 computations are allowed to be executed in the  MultiPass monad. w Global context  Instrument  !"#$%&' Prologue Algorithm body  Epilogue ()*Number of threads to spawn Element range +Number of threads to spawn Element range ,-  !"#$%&'()*+,-'"# !)*+,$%& (  T    !"#$%&'()*+,Safe-.This function provides a similar interface to  +, but is specifically for mapping over the   datatype in the   monad. ..This function provides a similar interface to  +, but is specifically for mapping over the   datatype in the   monad. /.This function provides a similar interface to   /, but is useful for mapping over a datatype in  a specific pass of the  monad.  Note: the m type is usually the   monad, but the implementation 3 does not specifically depend on anything from the  Control.Monad.MultiPass' library, so its type is more general. -Number of threads to spawn  Input array Mapping function  Output array .Number of threads to spawn  Input array Mapping function /-./-./-./Safe0&Test type for a four-pass instrument. 1'Test type for a three-pass instrument. 2%Test type for a two-pass instrument. 3%Test type for a one-pass instrument. 4)Test function for a one-pass instrument. 5)Test function for a two-pass instrument. 6+Test function for a three-pass instrument. 7*Test function for a four-pass instrument. 01234567012345674352617001234567Safe8%If the thread context is a pair then 8 creates a new  * function which can be used to update the  first element of the pair. 9%If the thread context is a pair then 9 creates a new  * function which can be used to update the  second element of the pair. :?If the thread context is an Either of two thread contexts then  : creates a new  function which  can be used to update the $ element. This function will assert  if the thread context is a  element. ;?If the thread context is an Either of two thread contexts then  ; creates a new  function which  can be used to update the $ element. This function will assert  if the thread context is a  element. 89:;89:;89:;89:;Safe <<1 is used during the second pass. It uses the log  which was computed by > to generate a series of unique  consecutive numbers. =&Get the current value of the counter. >>6 is used during the first pass. It builds up a log of @ the parallel tasks that were spawned, which is used during the A second pass to generate a series of unique consecutive numbers. ?&Get the current value of the counter. @Create a new counter. AIncrement the counter. BAdd k to the counter. CIncrement the counter. DAdd k to the counter. E Convert a > to a <. FBReset the counter to zero and rewind to the beginning of the log. <=>?@ABCDEF  <=>?@ABCDEF >??AB@<==CDEF<=>?@ABCDEF  SafeG@MonoidTC is a thread context which uses the Monoid interface to C combine the values from multiple threads. Instances of the Monoid @ class are expected to be associative, so the value computed by C MonoidTC is invariant under changes to the number of threads that  are spawned. GHI   GHIGHIGHI   SafeJ&Abstract datatype for the instrument. K&Get the current value of the counter. LAdd k to the counter. MIncrement the counter. N@Read and pre-increment the counter. For example, if the current  value is 17 then N( updates the value of the counter to 18  and returns 18. OARead and post-increment the counter. For example, if the current  value is 17 then O( updates the value of the counter to 18  and returns 17. JKLcounter k MNOJKLMNOJKLMNO JKLMNOSafeP&Abstract datatype for the instrument. QCreate a new array during pass p1, using the initialisation D function to initialise the elements. The initialisation is done in 2 parallel, using the specified number of threads. RR is a simple application of Q. It ! provides a similar interface to  !. The difference is D that it only executes the map operation once the specified pass is  reached. PQP instrument Number of threads to spawn Element range Initialisation function  New array RP instrument Number of threads to spawn  Input array "Function to apply to each element  Output array PQRPQRPQR SafeS&Abstract datatype for the instrument. TT, enables a value which was computed in pass p1 to be  used in pass p2. STSTSTST SafeU&Abstract datatype for the instrument. V.Execute the read-only computation during pass p1. WW is a simple application of V. It ) reads an index of the array during pass p1. This is particularly C useful if the array does not exist in earlier passes, for example  because it was created by the  "  instrument. UVW UVWUVWUVW SafeX&Abstract datatype for the instrument. Y>Initialise the base index of the output array. This method is E optional: if it is not called then the base index defaults to zero. Z'Write one element to the output array. [@Write a list of elements to the output array. The length of the A list needs to be declared in the first pass so that the correct & number of elements can be allocated. \+Get the current index in the output array. ]Get the output array. !"#$%&'X()*+,-Y Instrument  Base index Z Instrument Value to emit [ Instrument Length of the list List of elements to emit \ Instrument Current index ] Instrument  Output array ./0123456789XYZ[\]XYZ[\]!"#$%&'X()*+,-YZ[\]./0123456789 Safe^&Abstract datatype for the instrument. _>Initialise the base index of the output array. This method is E optional: if it is not called then the base index defaults to zero. `'Write one element to the output array. aBWrite a list of elements to the output array. The instrument uses @ back-tracking to iterate until the length of the list has been  determined. It is the client'$s responsibility to ensure that any D operations which depend on the length of the list are monotonic so A that a fixed point will be found. The first argument is used to > supply a minimum length for the list (zero is always a valid B input). It can be used to shorten the time to convergence when a  good lower bound is known. b+Get the current index in the output array. cGet the output array. 9:;<=>?@ABCDEFGHIJKLMNOPQ^RSTUVW_ Instrument  Base index ` Instrument Value to emit a Instrument Length of the list List of elements to emit b Instrument Current index c Instrument  Output array XYZ[\]^_`abcdefghijkl^_`abc^_`abc!:;<=>?@ABCDEFGHIJKLMNOPQ^RSTUVW_`abcXYZ[\]^_`abcdefghijkl Safed&Abstract datatype for the instrument. e(Tie the knot for the supplied function. mndopeqrstuvwdede mndopeqrstuvwSafef&Abstract datatype for the instrument. g8Add a value to the global value, during the first pass. hBAdd a value to the global value, during the prologue of the first  pass. i/Read the global value, during the second pass. j>Read the global value, during the epilogue of the first pass. xyfz{|}g Instrument  Value to add h Instrument  Value to add i Instrument  Global value j Instrument  Global value ~fghijfgihj xyfz{|}ghij~Safe k"This datatype is a newtype around  a . It maps its  keys (of type a#) to a permutation of the integers 0..n-1, where  n is the number of keys. l&Abstract datatype for the instrument. mInitialise the l instrument with an k. This D method is optional. Ff this method is not used then the instrument # will be initialised with an empty k. n"Get a unique index for the value. oGet the final k. Empty k. pLookup an element. qAInsert an element. If the element is not in the map yet, then it  is assigned index n, where n$ is the original size of the table. r=Add multiple elements. The new elements are assigned indices  n..n+k-1, where n' is the original size of the table and k is C the number of new elements to be added. This function will assert 6 if any of the new elements are already in the table. !klm Instrument Initial table n Instrument Value  Unique index opqrklmnopqrlmnokpqrklmnopqrSafes&Abstract datatype for the instrument. t6Load the value that was stored during the first pass. u:Store a value during the epilogue of the first pass. This ) function should be called exactly once. stustustu stuSafevwxyz{|}~ vwxyz{|}~ |}z{vyxw~vyxwz{|}~Safe Safe Safe SafeVersion using lazy evaluation. Version using the Control.Monad.MultiPass library.  SafeSafeBinary tree datatype. 0Original algorithm, which uses lazy evaluation. New algorithm, using the Control.Monad.MultiPass library. %Second version of the new algorithm ( ), using the  d instrument, rather than s. $Third version of the new algorithm ( ), using the  f instrument. Safe##$%&'()*+,-./0123456789:;<<==>?@@AABCDEFGHIJ!KLMNOPQRSTUVWXYZ[\]^_`abcddefghij"kl m n o p q r s t u v w x s t u v w y z{|}~,234567Y[     " m     o           r     ! " # $ % & ' ( ) * + , -    .  / 0 1 2 2 3 4 5 6    7 8 9 : ; ; < x     ! = > ? @ A B C D E F G H I J K L M N O P Q R R y S T U V W X Y Z[[{\]^_`abcdefghijklmnnoopqrs%tuvwxyz{|[[}~_Control-Monad-MultiPass-0.1.0.0Control.Monad.MultiPassControl.Monad.MultiPass.Utils*Control.Monad.MultiPass.Utils.InstanceTest'Control.Monad.MultiPass.Utils.UpdateCtx/Control.Monad.MultiPass.ThreadContext.CounterTC.Control.Monad.MultiPass.ThreadContext.MonoidTC*Control.Monad.MultiPass.Instrument.Counter1Control.Monad.MultiPass.Instrument.CreateST2Array(Control.Monad.MultiPass.Instrument.Delay.Control.Monad.MultiPass.Instrument.DelayedLift/Control.Monad.MultiPass.Instrument.EmitST2Array2Control.Monad.MultiPass.Instrument.EmitST2ArrayFxp(Control.Monad.MultiPass.Instrument.Knot3*Control.Monad.MultiPass.Instrument.Monoid2*Control.Monad.MultiPass.Instrument.OrdCons*Control.Monad.MultiPass.Instrument.TopKnot)Control.Monad.MultiPass.Example.Assembler#Control.Monad.MultiPass.Example.CFG$Control.Monad.MultiPass.Example.CFG2'Control.Monad.MultiPass.Example.Counter(Control.Monad.MultiPass.Example.Localmin'Control.Monad.MultiPass.Example.OrdCons&Control.Monad.MultiPass.Example.Repmin/Control.Monad.MultiPass.Example.StringInterningCounterData.Functor.IdentityIdentityrepminMP Control.MonadmapMmapM_ T.Traversable mapST2ArrayMPCreateST2Array NumThreads BackTrack backtrackNextGlobalContextnextGlobalContextNextThreadContextnextThreadContextUpdateThreadContextST2ToMPWrapInstrument InstrumentcreateInstrument ThreadContextsplitThreadContextmergeThreadContext MultiPassMainMultiPassEpilogueMultiPassPrologue MultiPass MultiPassBase PassNumber StepDirection StepBackward StepReset StepForwardOffOnMultiPassAlgorithmunwrapMultiPassAlgorithmPassZPassS mkMultiPassmkMultiPassProloguemkMultiPassEpiloguemkMultiPassMainwrapInstrumentrun parallelMP parallelMP_readOnlyST2ToMPmapST2ArrayMP_pmapMTestInstrument4TestInstrument3TestInstrument2TestInstrument1testInstrument1testInstrument2testInstrument3testInstrument4 updateCtxFst updateCtxSnd updateCtxLeftupdateCtxRight CounterTC2 counterVal2 CounterTC1 counterVal1 newCounterTC1incrCounterTC1addkCounterTC1incrCounterTC2addkCounterTC2 newCounterTC2resetCounterTC2MonoidTCunwrapMonoidTCpeekaddkincrpreIncrpostIncrcreateST2ArraypmapST2ArrayMPDelaydelay DelayedLift delayedLiftreadST2ArrayMP EmitST2Array setBaseIndexemitemitListgetIndex getResultEmitST2ArrayFxpKnot3knot3Monoid2tell tellProloguelistenlistenEpilogue OrdConsTableOrdCons initOrdConsordConsgetOrdConsTablelookupOrdConsTableinsertOrdConsTablegrowOrdConsTableTopKnotloadstore InstructionAddImm8GotoLabelRegister LabelNameassembleNodeemitCFGTree convertTreeLeaflocalmin localminMP convertArrayrepmin repminMP2 repminMP3internStringArraybase Data.MaybeNothingControl-Monad-ST2-0.1.0.1Control.Monad.ST2ST2 RunPasses runPassesInstantiatePassesinstantiatePassesInitCtxinitCtx ApplyArgs applyArgsApplyArgapplyArgunwrapMultiPassEpilogueunwrapMultiPassPrologueunwrapMultiPassunwrapMultiPassBaseunwrapPassNumberParamArgNilArgCons mapArgConsincrPassNumber minPassNumberrunMultiPassMain updateCtxArgL updateCtxArgRupdateThreadContextTopparallelHelperparallelHelper_$fRunPassesrwPassStc0gc0qout$fRunPassesrwPassZtcgcOnout$fBackTrackrwArgConsArgCons$fBackTrackrwArgNilArgNil$fBackTrackrwtc()$fInstantiatePassesPassSb$fInstantiatePassesPassZa#$fNextGlobalContextrwtcEitherEither$fNextGlobalContextrwtc(,,)(,,)$fNextGlobalContextrwtc(,)(,)$fNextGlobalContextrwtcgc()#$fNextThreadContextrwEithergcEither$fNextThreadContextrw()gc(,,)$fNextThreadContextrw(,,)gc(,,)$fNextThreadContextrw()gc(,)$fNextThreadContextrw(,)gc(,)$fNextThreadContextrwtcgc()$fInitCtxArgCons$fInitCtxArgNil $fInitCtx()E$fApplyArgsrwMultiPassMainArgNilArgNilArgNilArgNilrootTCMultiPassMain($fApplyArgsrwParamoldTColdGCtcgcrootTCf''$fApplyArgsrw(->)oldTColdGCtcgcrootTCf';$fApplyArgrwparaminstrfArgConsArgConsArgConsArgConsrootTCf'$fMonadWrapInstrument$fThreadContextrwEither$fThreadContextrw(,,)$fThreadContextrw(,)$fThreadContextrwArgCons$fThreadContextrwArgNil$fThreadContextrw()$fMonadMultiPassEpilogue$fMonadMultiPassPrologue$fMonadMultiPass$fMonadMultiPassBase $fMonadOff $fMonadOnST2Array WrappedType4UnwrappedType4 WrappedType3UnwrappedType3 WrappedType2UnwrappedType2 WrappedType1UnwrappedType1 testBody1 testBody2 testBody3 testBody4$$fMultiPassAlgorithmWrappedType4(->)$$fMultiPassAlgorithmWrappedType3(->)$$fMultiPassAlgorithmWrappedType2(->)$$fMultiPassAlgorithmWrappedType1(->) Data.EitherLeftRightcross counterLog2 counterIdx2 counterLog1CounterLogParallelCounterLogSequentialmkCounterLogSequential+$fNextThreadContextrwCounterTC2gcCounterTC2+$fNextThreadContextrwCounterTC2gcCounterTC1+$fNextThreadContextrwCounterTC1gcCounterTC2$fThreadContextrwCounterTC2+$fNextThreadContextrwCounterTC1gcCounterTC1#$fNextThreadContextrw()gcCounterTC1$fThreadContextrwCounterTC1!$fNextThreadContextrwtcgcMonoidTC$fThreadContextrwMonoidTC$fMonoidMonoidTC peekInternal addkInternal!$fInstrumenttcCounterTC2()Counter!$fInstrumenttcCounterTC1()Counter$fInstrumenttc()()CountercreateInternal $fInstrumenttc()()CreateST2Array!$fInstrumenttc()()CreateST2Array0 delayInternal$fInstrumenttc()()Delay$fInstrumenttc()()Delay0$fInstrumenttc()()Delay1delayedLiftInternal$fInstrumenttc()()DelayedLift$fInstrumenttc()()DelayedLift0GC3gc3_basegc3_output_arrayGC2gc2_basesetBaseInternal emitInternalemitListInternalgetIndexInternalgetResultInternal%$fNextGlobalContextrwCounterTC2GC3GC2%$fNextGlobalContextrwCounterTC2GC3GC3%$fNextGlobalContextrwCounterTC2GC2GC3$fNextGlobalContextrwtcGC2GC2%$fNextGlobalContextrwCounterTC1GC2GC3$fNextGlobalContextrwtc()GC2$fBackTrackrwCounterTC2GC3$fBackTrackrwCounterTC2GC2'$fInstrumenttcCounterTC2GC3EmitST2Array'$fInstrumenttcCounterTC2GC2EmitST2Array&$fInstrumenttcCounterTC1()EmitST2Array$fInstrumenttc()()EmitST2Arraygc3_length_array gc3_readygc3_passnumber2gc3_passnumber3TC3 indexCounter listCounternewIndexCounter indexChangedgc2_initialisedgc2_length_arraygc2_passnumberTC2 ListIndexTC1updateIndexCounterupdateListCounterupdateNewIndexCounterupdateIndexChanged$fNextThreadContextrwTC3gc(,)$fNextThreadContextrw(,)gcTC3$fNextGlobalContextrwTC3GC3GC2$fNextGlobalContextrwTC3GC3GC3$fNextGlobalContextrw(,)GC2GC3$fNextGlobalContextrw(,)GC2GC2$fNextGlobalContextrw(,)()GC2$fNextThreadContextrwTC3gcTC3$fBackTrackrwTC3GC3$fBackTrackrw(,)GC2#$fInstrumenttcTC3GC3EmitST2ArrayFxp$fThreadContextrwTC3#$fInstrumenttc(,)GC2EmitST2ArrayFxp"$fInstrumenttc(,)()EmitST2ArrayFxp$fShowListIndex$fNumListIndex!$fInstrumenttc()()EmitST2ArrayFxpBuffer knot3Internal#$fNextGlobalContextrwtcBufferBuffer'$fNextGlobalContextrwCounterTC1()Buffer$fBackTrackrwtcBuffer#$fInstrumenttcCounterTC2BufferKnot3$$fInstrumenttcCounterTC2BufferKnot30$fInstrumenttcCounterTC1()Knot3$fInstrumenttc()()Knot3GC tellInternallistenInternallistenInternalEpilogue$fNextGlobalContextrw()GCGC!$fNextGlobalContextrwMonoidTC()GC$fBackTrackrw()GC$fInstrumenttc()GCMonoid2$fInstrumenttcMonoidTC()Monoid2$fInstrumenttc()()Monoid2containers-0.5.0.0 Data.Map.BaseMapghc-prim GHC.TypesIntemptyOrdConsTable gc2_initTable gc2_newTable OrdConsTCGC1 initInternalordConsInternalgetOrdConsTableInternal$fNextGlobalContextrwtcGC2GC1#$fNextGlobalContextrwMonoidTCGC1GC2$fNextGlobalContextrwtcGC1GC1$fNextGlobalContextrw()()GC1$fBackTrackrw()GC2$fBackTrackrwtcGC1$fInstrumenttc()GC2OrdCons $fInstrumenttcMonoidTCGC1OrdCons$fInstrumenttc()()OrdCons$fMonoidOrdConsTC loadInternal storeInternal$fNextGlobalContextrw()()GC$fBackTrackrwtcGC$fInstrumenttc()GCTopKnot$fInstrumenttc()GCTopKnot0$fInstrumenttc()()TopKnot EmitInstrsEmitInstrsTypeLabelMapAddr lookupLabelsingletonLabelMap emitInstrencodeOpcodeWithREX emitInt32emitWord emitRegisterfitsSignedInt8 signExtend8"$fMultiPassAlgorithmEmitInstrs(->)$fMonoidLabelMap $fShowAddr $fNumAddr$fShowRegister$fShowLabelNameEmitCFG EmitCFGTypePositionCFGemitMain emitNodesemitNode positionDiff$fMultiPassAlgorithmEmitCFG(->) $fNumPosition $fNumNodeConvertTreeType ConvertTree convertTreeMPconvertSubTree#$fMultiPassAlgorithmConvertTree(->)Localmin LocalminType localminWalk localminTopMPlocalminWalkMP $fMultiPassAlgorithmLocalmin(->)ConvertArrayType ConvertArrayconvertArrayMP$$fMultiPassAlgorithmConvertArray(->)MinVal getMinValInfinityRepmin3 RepminType3Repmin2 RepminType2Repmin RepminType repminWalk repminWalkMP repminWalkMP3$fMonoidMinVal$fMultiPassAlgorithmRepmin3(->)$fMultiPassAlgorithmRepmin2(->)$fMultiPassAlgorithmRepmin(->)InternArrayType InternArrayinternStringArrayElems#$fMultiPassAlgorithmInternArray(->)