    -- | Optimisation pipelines.
    module Futhark.Passes
      ( standardPipeline,
        seqPipeline,
        gpuPipeline,
        seqmemPipeline,
        gpumemPipeline,
        mcPipeline,
        mcmemPipeline,
      )
    where

    import Control.Category ((>>>))
    import Futhark.IR.GPU (GPU)
    import Futhark.IR.GPUMem (GPUMem)
    import Futhark.IR.MC (MC)
    import Futhark.IR.MCMem (MCMem)
    import Futhark.IR.SOACS (SOACS, usesAD)
    import Futhark.IR.Seq (Seq)
    import Futhark.IR.SeqMem (SeqMem)
    import Futhark.Optimise.ArrayLayout
    import Futhark.Optimise.ArrayShortCircuiting qualified as ArrayShortCircuiting
    import Futhark.Optimise.CSE
    import Futhark.Optimise.DoubleBuffer
    import Futhark.Optimise.EntryPointMem
    import Futhark.Optimise.Fusion
    import Futhark.Optimise.GenRedOpt
    import Futhark.Optimise.HistAccs
    import Futhark.Optimise.InliningDeadFun
    import Futhark.Optimise.MemoryBlockMerging qualified as MemoryBlockMerging
    import Futhark.Optimise.MergeGPUBodies
    import Futhark.Optimise.ReduceDeviceSyncs
    import Futhark.Optimise.Sink
    import Futhark.Optimise.TileLoops
    import Futhark.Optimise.Unstream
    import Futhark.Pass.AD
    import Futhark.Pass.ExpandAllocations
    import Futhark.Pass.ExplicitAllocations.GPU qualified as GPU
    import Futhark.Pass.ExplicitAllocations.MC qualified as MC
    import Futhark.Pass.ExplicitAllocations.Seq qualified as Seq
    import Futhark.Pass.ExtractKernels
    import Futhark.Pass.ExtractMulticore
    import Futhark.Pass.FirstOrderTransform
    import Futhark.Pass.LiftAllocations as LiftAllocations
    import Futhark.Pass.LowerAllocations as LowerAllocations
    import Futhark.Pass.Simplify
    import Futhark.Pipeline

    -- | A pipeline used by all current compilers.  Performs inlining,
    -- fusion, and various forms of cleanup.  This pipeline will be
    -- followed by another one that deals with parallelism and memory.
    standardPipeline :: Pipeline SOACS SOACS
    standardPipeline :: Pipeline SOACS SOACS
    standardPipeline =
      [Pass SOACS SOACS] -> Pipeline SOACS SOACS
    forall rep. Checkable rep => [Pass rep rep] -> Pipeline rep rep
    passes
        [ Pass SOACS SOACS
    simplifySOACS,
          Pass SOACS SOACS
    inlineConservatively,
          Pass SOACS SOACS
    simplifySOACS,
          Pass SOACS SOACS
    inlineAggressively,
          Pass SOACS SOACS
    simplifySOACS,
          Bool -> Pass SOACS SOACS
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    True,
          Pass SOACS SOACS
    simplifySOACS,
          Pass SOACS SOACS
    fuseSOACs,
          Bool -> Pass SOACS SOACS
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    True,
          Pass SOACS SOACS
    simplifySOACS,
          Pass SOACS SOACS
    removeDeadFunctions
        ]
        Pipeline SOACS SOACS
    -> Pipeline SOACS SOACS -> Pipeline SOACS SOACS
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> (Prog SOACS -> Bool)
    -> Pipeline SOACS SOACS -> Pipeline SOACS SOACS
    forall rep.
    (Prog rep -> Bool) -> Pipeline rep rep -> Pipeline rep rep
    condPipeline Prog SOACS -> Bool
    usesAD Pipeline SOACS SOACS
    adPipeline

    -- | This is the pipeline that applies the AD transformation and
    -- subsequent interesting optimisations.
    adPipeline :: Pipeline SOACS SOACS
    adPipeline :: Pipeline SOACS SOACS
    adPipeline =
      [Pass SOACS SOACS] -> Pipeline SOACS SOACS
    forall rep. Checkable rep => [Pass rep rep] -> Pipeline rep rep
    passes
        [ Pass SOACS SOACS
    applyAD,
          Pass SOACS SOACS
    simplifySOACS,
          Bool -> Pass SOACS SOACS
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    True,
          Pass SOACS SOACS
    fuseSOACs,
          Bool -> Pass SOACS SOACS
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    True,
          Pass SOACS SOACS
    simplifySOACS
        ]

    -- | The pipeline used by the CUDA, HIP, and OpenCL backends, but before
    -- adding memory information.  Includes 'standardPipeline'.
    gpuPipeline :: Pipeline SOACS GPU
    gpuPipeline :: Pipeline SOACS GPU
    gpuPipeline =
      Pipeline SOACS SOACS
    standardPipeline
        Pipeline SOACS SOACS -> Pipeline SOACS GPU -> Pipeline SOACS GPU
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> Pass SOACS GPU -> Pipeline SOACS GPU
    forall torep fromrep.
    Checkable torep =>
    Pass fromrep torep -> Pipeline fromrep torep
    onePass Pass SOACS GPU
    extractKernels
        Pipeline SOACS GPU -> Pipeline GPU GPU -> Pipeline SOACS GPU
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> [Pass GPU GPU] -> Pipeline GPU GPU
    forall rep. Checkable rep => [Pass rep rep] -> Pipeline rep rep
    passes
          [ Pass GPU GPU
    simplifyGPU,
            Pass GPU GPU
    optimiseGenRed,
            Pass GPU GPU
    simplifyGPU,
            Pass GPU GPU
    tileLoops,
            Pass GPU GPU
    simplifyGPU,
            Pass GPU GPU
    histAccsGPU,
            Pass GPU GPU
    unstreamGPU,
            Bool -> Pass GPU GPU
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    True,
            Pass GPU GPU
    simplifyGPU,
            Pass GPU GPU
    sinkGPU, -- Sink reads before migrating them.
            Pass GPU GPU
    reduceDeviceSyncs,
            Pass GPU GPU
    simplifyGPU, -- Simplify and hoist storages.
            Bool -> Pass GPU GPU
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    True, -- Eliminate duplicate storages.
            Pass GPU GPU
    mergeGPUBodies,
            Pass GPU GPU
    simplifyGPU, -- Cleanup merged GPUBody kernels.
            Pass GPU GPU
    sinkGPU, -- Sink reads within GPUBody kernels.
            Pass GPU GPU
    optimiseArrayLayoutGPU,
            -- Important to simplify after coalescing in order to fix up
            -- redundant manifests.
            Pass GPU GPU
    simplifyGPU,
            Bool -> Pass GPU GPU
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    True
          ]

    -- | The pipeline used by the sequential backends.  Turns all
    -- parallelism into sequential loops.  Includes 'standardPipeline'.
    seqPipeline :: Pipeline SOACS Seq
    seqPipeline :: Pipeline SOACS Seq
    seqPipeline =
      Pipeline SOACS SOACS
    standardPipeline
        Pipeline SOACS SOACS -> Pipeline SOACS Seq -> Pipeline SOACS Seq
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> Pass SOACS Seq -> Pipeline SOACS Seq
    forall torep fromrep.
    Checkable torep =>
    Pass fromrep torep -> Pipeline fromrep torep
    onePass Pass SOACS Seq
    forall rep. FirstOrderRep rep => Pass SOACS rep
    firstOrderTransform
        Pipeline SOACS Seq -> Pipeline Seq Seq -> Pipeline SOACS Seq
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> [Pass Seq Seq] -> Pipeline Seq Seq
    forall rep. Checkable rep => [Pass rep rep] -> Pipeline rep rep
    passes
          [ Pass Seq Seq
    simplifySeq
          ]

    -- | Run 'seqPipeline', then add memory information (and
    -- optimise it slightly).
    seqmemPipeline :: Pipeline SOACS SeqMem
    seqmemPipeline :: Pipeline SOACS SeqMem
    seqmemPipeline =
      Pipeline SOACS Seq
    seqPipeline
        Pipeline SOACS Seq -> Pipeline Seq SeqMem -> Pipeline SOACS SeqMem
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> Pass Seq SeqMem -> Pipeline Seq SeqMem
    forall torep fromrep.
    Checkable torep =>
    Pass fromrep torep -> Pipeline fromrep torep
    onePass Pass Seq SeqMem
    Seq.explicitAllocations
        Pipeline Seq SeqMem
    -> Pipeline SeqMem SeqMem -> Pipeline Seq SeqMem
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> [Pass SeqMem SeqMem] -> Pipeline SeqMem SeqMem
    forall rep. Checkable rep => [Pass rep rep] -> Pipeline rep rep
    passes
          [ Bool -> Pass SeqMem SeqMem
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    False,
            Pass SeqMem SeqMem
    simplifySeqMem,
            Pass SeqMem SeqMem
    entryPointMemSeq,
            Pass SeqMem SeqMem
    simplifySeqMem,
            Pass SeqMem SeqMem
    LiftAllocations.liftAllocationsSeqMem,
            Pass SeqMem SeqMem
    simplifySeqMem,
            Pass SeqMem SeqMem
    ArrayShortCircuiting.optimiseSeqMem,
            Pass SeqMem SeqMem
    simplifySeqMem,
            Bool -> Pass SeqMem SeqMem
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    False,
            Pass SeqMem SeqMem
    simplifySeqMem,
            Pass SeqMem SeqMem
    LowerAllocations.lowerAllocationsSeqMem,
            Pass SeqMem SeqMem
    simplifySeqMem
          ]

    -- | Run 'gpuPipeline', then add memory information (and optimise
    -- it a lot).
    gpumemPipeline :: Pipeline SOACS GPUMem
    gpumemPipeline :: Pipeline SOACS GPUMem
    gpumemPipeline =
      Pipeline SOACS GPU
    gpuPipeline
        Pipeline SOACS GPU -> Pipeline GPU GPUMem -> Pipeline SOACS GPUMem
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> Pass GPU GPUMem -> Pipeline GPU GPUMem
    forall torep fromrep.
    Checkable torep =>
    Pass fromrep torep -> Pipeline fromrep torep
    onePass Pass GPU GPUMem
    GPU.explicitAllocations
        Pipeline GPU GPUMem
    -> Pipeline GPUMem GPUMem -> Pipeline GPU GPUMem
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> [Pass GPUMem GPUMem] -> Pipeline GPUMem GPUMem
    forall rep. Checkable rep => [Pass rep rep] -> Pipeline rep rep
    passes
          [ Pass GPUMem GPUMem
    simplifyGPUMem,
            Bool -> Pass GPUMem GPUMem
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    False,
            Pass GPUMem GPUMem
    simplifyGPUMem,
            Pass GPUMem GPUMem
    entryPointMemGPU,
            Pass GPUMem GPUMem
    doubleBufferGPU,
            Pass GPUMem GPUMem
    simplifyGPUMem,
            Bool -> Pass GPUMem GPUMem
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    False,
            Pass GPUMem GPUMem
    LiftAllocations.liftAllocationsGPUMem,
            Pass GPUMem GPUMem
    simplifyGPUMem,
            Pass GPUMem GPUMem
    ArrayShortCircuiting.optimiseGPUMem,
            Pass GPUMem GPUMem
    simplifyGPUMem,
            Bool -> Pass GPUMem GPUMem
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    False,
            Pass GPUMem GPUMem
    simplifyGPUMem,
            Pass GPUMem GPUMem
    LowerAllocations.lowerAllocationsGPUMem,
            Bool -> Pass GPUMem GPUMem
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    False,
            Pass GPUMem GPUMem
    simplifyGPUMem,
            Pass GPUMem GPUMem
    MemoryBlockMerging.optimise,
            Pass GPUMem GPUMem
    simplifyGPUMem,
            Pass GPUMem GPUMem
    expandAllocations,
            Pass GPUMem GPUMem
    simplifyGPUMem
          ]

    -- | Run 'standardPipeline' and then convert to multicore
    -- representation (and do a bunch of optimisation).
    mcPipeline :: Pipeline SOACS MC
    mcPipeline :: Pipeline SOACS MC
    mcPipeline =
      Pipeline SOACS SOACS
    standardPipeline
        Pipeline SOACS SOACS -> Pipeline SOACS MC -> Pipeline SOACS MC
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> Pass SOACS MC -> Pipeline SOACS MC
    forall torep fromrep.
    Checkable torep =>
    Pass fromrep torep -> Pipeline fromrep torep
    onePass Pass SOACS MC
    extractMulticore
        Pipeline SOACS MC -> Pipeline MC MC -> Pipeline SOACS MC
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> [Pass MC MC] -> Pipeline MC MC
    forall rep. Checkable rep => [Pass rep rep] -> Pipeline rep rep
    passes
          [ Pass MC MC
    simplifyMC,
            Pass MC MC
    unstreamMC,
            Bool -> Pass MC MC
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    True,
            Pass MC MC
    simplifyMC,
            Pass MC MC
    sinkMC,
            Pass MC MC
    optimiseArrayLayoutMC,
            Pass MC MC
    simplifyMC,
            Bool -> Pass MC MC
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    True
          ]

    -- | Run 'mcPipeline' and then add memory information.
    mcmemPipeline :: Pipeline SOACS MCMem
    mcmemPipeline :: Pipeline SOACS MCMem
    mcmemPipeline =
      Pipeline SOACS MC
    mcPipeline
        Pipeline SOACS MC -> Pipeline MC MCMem -> Pipeline SOACS MCMem
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> Pass MC MCMem -> Pipeline MC MCMem
    forall torep fromrep.
    Checkable torep =>
    Pass fromrep torep -> Pipeline fromrep torep
    onePass Pass MC MCMem
    MC.explicitAllocations
        Pipeline MC MCMem -> Pipeline MCMem MCMem -> Pipeline MC MCMem
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> [Pass MCMem MCMem] -> Pipeline MCMem MCMem
    forall rep. Checkable rep => [Pass rep rep] -> Pipeline rep rep
    passes
          [ Pass MCMem MCMem
    simplifyMCMem,
            Bool -> Pass MCMem MCMem
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    False,
            Pass MCMem MCMem
    simplifyMCMem,
            Pass MCMem MCMem
    entryPointMemMC,
            Pass MCMem MCMem
    doubleBufferMC,
            Pass MCMem MCMem
    simplifyMCMem,
            Bool -> Pass MCMem MCMem
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    False,
            Pass MCMem MCMem
    LiftAllocations.liftAllocationsMCMem,
            Pass MCMem MCMem
    simplifyMCMem,
            Pass MCMem MCMem
    ArrayShortCircuiting.optimiseMCMem,
            Pass MCMem MCMem
    simplifyMCMem,
            Bool -> Pass MCMem MCMem
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    False,
            Pass MCMem MCMem
    simplifyMCMem,
            Pass MCMem MCMem
    LowerAllocations.lowerAllocationsMCMem,
            Bool -> Pass MCMem MCMem
    forall rep.
    (AliasableRep rep, CSEInOp (Op (Aliases rep))) =>
    Bool -> Pass rep rep
    performCSE Bool
    False,
            Pass MCMem MCMem
    simplifyMCMem
          ]