+availRegsLattice :: DataflowLattice AvailRegs
+availRegsLattice = DataflowLattice "register gotten from reloads" empty add False
+ -- last True <==> debugging on
+ where empty = UniverseMinus emptyRegSet
+ -- | compute in the Tx monad to track whether anything has changed
+ add new old =
+ let join = interAvail new old in
+ if join `smallerAvail` old then aTx join else noTx join
+
+
+interAvail :: AvailRegs -> AvailRegs -> AvailRegs
+interAvail (UniverseMinus s) (UniverseMinus s') = UniverseMinus (s `plusRegSet` s')
+interAvail (AvailRegs s) (AvailRegs s') = AvailRegs (s `timesRegSet` s')
+interAvail (AvailRegs s) (UniverseMinus s') = AvailRegs (s `minusRegSet` s')
+interAvail (UniverseMinus s) (AvailRegs s') = AvailRegs (s' `minusRegSet` s )
+
+smallerAvail :: AvailRegs -> AvailRegs -> Bool
+smallerAvail (AvailRegs _) (UniverseMinus _) = True
+smallerAvail (UniverseMinus _) (AvailRegs _) = False
+smallerAvail (AvailRegs s) (AvailRegs s') = sizeUniqSet s < sizeUniqSet s'
+smallerAvail (UniverseMinus s) (UniverseMinus s') = sizeUniqSet s > sizeUniqSet s'
+
+--extendAvail :: AvailRegs -> LocalReg -> AvailRegs
+--extendAvail (UniverseMinus s) r = UniverseMinus (deleteFromRegSet s r)
+--extendAvail (AvailRegs s) r = AvailRegs (extendRegSet s r)
+
+deleteFromAvail :: AvailRegs -> LocalReg -> AvailRegs
+deleteFromAvail (UniverseMinus s) r = UniverseMinus (extendRegSet s r)
+deleteFromAvail (AvailRegs s) r = AvailRegs (deleteFromRegSet s r)
+
+elemAvail :: AvailRegs -> LocalReg -> Bool
+elemAvail (UniverseMinus s) r = not $ elemRegSet r s
+elemAvail (AvailRegs s) r = elemRegSet r s
+
+type CmmAvail = BlockEnv AvailRegs
+type AvailFix = FuelMonad (ForwardFixedPoint Middle Last AvailRegs ())
+
+cmmAvailableReloads :: LGraph Middle Last -> FuelMonad CmmAvail
+cmmAvailableReloads g = liftM zdfFpFacts $ (res :: AvailFix)
+ where res = zdfSolveFromL emptyBlockEnv "available reloads" availRegsLattice
+ avail_reloads_transfer empty g
+ empty = fact_bot availRegsLattice
+
+avail_reloads_transfer :: ForwardTransfers Middle Last AvailRegs
+avail_reloads_transfer = ForwardTransfers first middle last id
+ where first avail _ = avail
+ middle = flip middleAvail
+ last = lastAvail
+
+-- | The transfer equations use the traditional 'gen' and 'kill'
+-- notations, which should be familiar from the dragon book.
+--agen,
+akill :: UserOfLocalRegs a => a -> AvailRegs -> AvailRegs
+--agen a live = foldRegsUsed extendAvail live a
+akill a live = foldRegsUsed deleteFromAvail live a
+
+-- Note: you can't sink the reload past a use.
+middleAvail :: Middle -> AvailRegs -> AvailRegs
+middleAvail m = middle m
+ where middle m live = middle' m $ foldRegsUsed deleteFromAvail live m
+ middle' (MidComment {}) live = live
+ middle' (MidAssign lhs _expr) live = akill lhs live
+ middle' (MidStore {}) live = live
+ middle' (MidForeignCall {}) _ = AvailRegs emptyRegSet
+
+lastAvail :: AvailRegs -> Last -> LastOutFacts AvailRegs
+lastAvail _ (LastCall _ (Just k) _ _) = LastOutFacts [(k, AvailRegs emptyRegSet)]
+lastAvail avail l = LastOutFacts $ map (\id -> (id, avail)) $ succs l
+
+type LateReloadFix = FuelMonad (ForwardFixedPoint Middle Last AvailRegs CmmGraph)
+
+insertLateReloads :: (LGraph Middle Last) -> FuelMonad (LGraph Middle Last)
+insertLateReloads g = liftM zdfFpContents $ (res :: LateReloadFix)
+ where res = zdfFRewriteFromL RewriteShallow emptyBlockEnv "insert late reloads"
+ availRegsLattice avail_reloads_transfer rewrites bot g
+ bot = fact_bot availRegsLattice
+ rewrites = ForwardRewrites first middle last exit
+ first _ _ = Nothing
+ middle :: AvailRegs -> Middle -> Maybe (AGraph Middle Last)
+ last :: AvailRegs -> Last -> Maybe (AGraph Middle Last)
+ middle avail m = maybe_reload_before avail m (ZTail m (ZLast LastExit))
+ last avail l = maybe_reload_before avail l (ZLast (LastOther l))
+ exit _ = Nothing
+ maybe_reload_before avail node tail =
+ let used = filterRegsUsed (elemAvail avail) node
+ in if isEmptyUniqSet used then Nothing
+ else Just $ mkZTail $ reloadTail used tail
+
+removeDeadAssignmentsAndReloads :: BlockSet -> (LGraph Middle Last) -> FuelMonad (LGraph Middle Last)
+removeDeadAssignmentsAndReloads procPoints g@(LGraph entry _ _) =
+ liftM zdfFpContents $ (res :: LiveReloadFix (LGraph Middle Last))
+ where res = zdfBRewriteFromL RewriteDeep emptyBlockEnv "dead-assignment & -reload elim"
+ dualLiveLattice (dualLiveTransfers entry procPoints)
+ rewrites (fact_bot dualLiveLattice) g
+ rewrites = BackwardRewrites first middle last exit
+ exit = Nothing
+ last = \_ _ -> Nothing
+ middle = middleRemoveDeads
+ first _ _ = Nothing
+
+middleRemoveDeads :: DualLive -> Middle -> Maybe (AGraph Middle Last)
+middleRemoveDeads live m = middle m
+ where middle (MidAssign (CmmLocal reg') _)
+ | not (reg' `elemRegSet` in_regs live) = Just emptyAGraph
+ middle _ = Nothing
+
+
+
+---------------------
+-- prettyprinting