From 7979153412d385545e9a43e1bb65419028cfec88 Mon Sep 17 00:00:00 2001 From: Simon Marlow Date: Tue, 23 Jan 2007 10:40:25 +0000 Subject: [PATCH] Fix a bug in the liveness analysis We were being overly conservative, registers that were live only at a branch target were not recorded as being dead in the branch-not-taken code. --- compiler/nativeGen/RegisterAlloc.hs | 29 ++++++++++++++++++++--------- 1 file changed, 20 insertions(+), 9 deletions(-) diff --git a/compiler/nativeGen/RegisterAlloc.hs b/compiler/nativeGen/RegisterAlloc.hs index 2031fa7..0a732fb 100644 --- a/compiler/nativeGen/RegisterAlloc.hs +++ b/compiler/nativeGen/RegisterAlloc.hs @@ -353,7 +353,10 @@ computeLiveness sccs liveness liveregs blockmap done [] = (liveregs, done) liveness liveregs blockmap done (instr:instrs) - = liveness liveregs2 blockmap ((instr,r_dying,w_dying):done) instrs + | not_a_branch = liveness liveregs1 blockmap + ((instr,r_dying,w_dying):done) instrs + | otherwise = liveness liveregs_br blockmap + ((instr,r_dying_br,w_dying):done) instrs where RU read written = regUsage instr @@ -362,24 +365,32 @@ computeLiveness sccs liveregs1 = (liveregs `delListFromUniqSet` written) `addListToUniqSet` read + -- registers that are not live beyond this point, are recorded + -- as dying here. + r_dying = [ reg | reg <- read, reg `notElem` written, + not (elementOfUniqSet reg liveregs) ] + + w_dying = [ reg | reg <- written, + not (elementOfUniqSet reg liveregs) ] + -- union in the live regs from all the jump destinations of this -- instruction. targets = jumpDests instr [] -- where we go from here - liveregs2 = unionManyUniqSets - (liveregs1 : map targetLiveRegs targets) + not_a_branch = null targets targetLiveRegs target = case lookupUFM blockmap target of Just ra -> ra Nothing -> emptyBlockMap - -- registers that are not live beyond this point, are recorded - -- as dying here. - r_dying = [ reg | reg <- read, reg `notElem` written, - not (elementOfUniqSet reg liveregs) ] + live_from_branch = unionManyUniqSets (map targetLiveRegs targets) - w_dying = [ reg | reg <- written, - not (elementOfUniqSet reg liveregs) ] + liveregs_br = liveregs1 `unionUniqSets` live_from_branch + -- registers that are live only in the branch targets should + -- be listed as dying here. + live_branch_only = live_from_branch `minusUniqSet` liveregs + r_dying_br = uniqSetToList (mkUniqSet r_dying `unionUniqSets` + live_branch_only) -- ----------------------------------------------------------------------------- -- Linear sweep to allocate registers -- 1.7.10.4