1 module CmmBrokenBlock (
6 cmmBlockFromBrokenBlock,
10 #include "HsVersions.h"
20 -----------------------------------------------------------------------------
22 -----------------------------------------------------------------------------
24 -- |Similar to a 'CmmBlock' with a little extra information
25 -- to help the CPS analysis.
28 brokenBlockId :: BlockId, -- ^ The block's label like a 'CmmBasicBlock'
29 brokenBlockEntry :: BlockEntryInfo,
30 -- ^ Ways this block can be entered
32 brokenBlockStmts :: [CmmStmt],
33 -- ^ Body like a CmmBasicBlock
34 -- (but without the last statement)
36 brokenBlockTargets :: [BlockId],
37 -- ^ Blocks that this block could
38 -- branch to one either by conditional
39 -- branches or via the last statement
41 brokenBlockExit :: FinalStmt
42 -- ^ The final statement of the block
45 -- | How a block could be entered
47 = FunctionEntry -- ^ Block is the beginning of a function
48 CLabel -- ^ The function name
49 CmmFormals -- ^ Aguments to function
51 | ContinuationEntry -- ^ Return point of a function call
52 CmmFormals -- ^ return values (argument to continuation)
54 | ControlEntry -- ^ Any other kind of block.
55 -- Only entered due to control flow.
57 -- TODO: Consider adding ProcPointEntry
58 -- no return values, but some live might end up as
59 -- params or possibly in the frame
62 -- | Final statement in a 'BlokenBlock'.
63 -- Constructors and arguments match those in 'Cmm',
64 -- but are restricted to branches, returns, jumps, calls and switches
66 = FinalBranch -- ^ Same as 'CmmBranch'
67 BlockId -- ^ Target must be a ControlEntry
69 | FinalReturn -- ^ Same as 'CmmReturn'
70 CmmActuals -- ^ Return values
72 | FinalJump -- ^ Same as 'CmmJump'
73 CmmExpr -- ^ The function to call
74 CmmActuals -- ^ Arguments of the call
76 | FinalCall -- ^ Same as 'CmmForeignCall'
77 -- followed by 'CmmGoto'
78 BlockId -- ^ Target of the 'CmmGoto'
79 -- (must be a 'ContinuationEntry')
80 CmmCallTarget -- ^ The function to call
81 CmmFormals -- ^ Results from call
82 -- (redundant with ContinuationEntry)
83 CmmActuals -- ^ Arguments to call
84 (Maybe [GlobalReg]) -- ^ registers that must be saved (TODO)
86 | FinalSwitch -- ^ Same as a 'CmmSwitch'
87 CmmExpr -- ^ Scrutinee (zero based)
88 [Maybe BlockId] -- ^ Targets
90 -----------------------------------------------------------------------------
91 -- Operations for broken blocks
92 -----------------------------------------------------------------------------
94 -----------------------------------------------------------------------------
95 -- | Takes a 'CmmBasicBlock' and breaks it up into a list of 'BrokenBlock'
96 -- by splitting on each 'CmmCall' in the 'CmmBasicBlock'.
99 [Unique] -- ^ An infinite list of uniques
100 -- to create names of the new blocks with
101 -> CmmBasicBlock -- ^ Input block to break apart
102 -> BlockEntryInfo -- ^ Info for the first created 'BrokenBlock'
104 breakBlock uniques (BasicBlock ident stmts) entry =
105 breakBlock' uniques ident entry [] [] stmts
107 breakBlock' uniques current_id entry exits accum_stmts stmts =
109 [] -> panic "block doesn't end in jump, goto, return or switch"
110 [CmmJump target arguments] ->
111 [BrokenBlock current_id entry accum_stmts
113 (FinalJump target arguments)]
114 [CmmReturn arguments] ->
115 [BrokenBlock current_id entry accum_stmts
117 (FinalReturn arguments)]
118 [CmmBranch target] ->
119 [BrokenBlock current_id entry accum_stmts
121 (FinalBranch target)]
122 [CmmSwitch expr targets] ->
123 [BrokenBlock current_id entry accum_stmts
124 (mapMaybe id targets ++ exits)
125 (FinalSwitch expr targets)]
126 (CmmJump _ _:_) -> panic "jump in middle of block"
127 (CmmReturn _:_) -> panic "return in middle of block"
128 (CmmBranch _:_) -> panic "branch in middle of block"
129 (CmmSwitch _ _:_) -> panic "switch in middle of block"
131 -- Detect this special case to remain an inverse of
132 -- 'cmmBlockFromBrokenBlock'
133 [CmmCall target results arguments saves,
134 CmmBranch next_id] -> [block]
136 block = do_call current_id entry accum_stmts exits next_id
137 target results arguments saves
138 (CmmCall target results arguments saves:stmts) -> block : rest
140 next_id = BlockId $ head uniques
141 block = do_call current_id entry accum_stmts exits next_id
142 target results arguments saves
143 rest = breakBlock' (tail uniques) next_id
144 (ContinuationEntry results) [] [] stmts
146 breakBlock' uniques current_id entry
147 (cond_branch_target s++exits)
151 do_call current_id entry accum_stmts exits next_id
152 target results arguments saves =
153 BrokenBlock current_id entry accum_stmts (next_id:exits)
154 (FinalCall next_id target results arguments saves)
156 cond_branch_target (CmmCondBranch _ target) = [target]
157 cond_branch_target _ = []
159 -----------------------------------------------------------------------------
160 -- | Convert from a BrokenBlock back to an equivalent CmmBasicBlock
161 -- Needed by liveness analysis
162 cmmBlockFromBrokenBlock :: BrokenBlock -> CmmBasicBlock
163 cmmBlockFromBrokenBlock (BrokenBlock ident _ stmts _ exit) =
164 BasicBlock ident (stmts++exit_stmt)
168 FinalBranch target -> [CmmBranch target]
169 FinalReturn arguments -> [CmmReturn arguments]
170 FinalJump target arguments -> [CmmJump target arguments]
171 FinalSwitch expr targets -> [CmmSwitch expr targets]
172 FinalCall branch_target call_target results arguments saves ->
173 [CmmCall call_target results arguments saves,
174 CmmBranch branch_target]
176 -----------------------------------------------------------------------------
177 -- | Build a mapping so we can lookup a 'BrokenBlock' by its 'BlockId'
178 blocksToBlockEnv :: [BrokenBlock] -> BlockEnv BrokenBlock
179 blocksToBlockEnv blocks = listToUFM $ map (\b -> (brokenBlockId b, b)) blocks