+ rec_edges :: [Node Details]
+ rec_edges = {-# SCC "occAnalBind.assoc" #-} map make_node pairs
+
+ make_node (bndr, rhs)
+ = (ND bndr rhs' rhs_usage rhs_fvs, idUnique bndr, out_edges)
+ where
+ (rhs_usage, rhs') = occAnalRhs env bndr rhs
+ rhs_fvs = intersectUFM_C (\b _ -> b) bndr_set rhs_usage
+ out_edges = keysUFM (rhs_fvs `unionVarSet` idRuleVars bndr)
+ -- (a -> b) means a mentions b
+ -- Given the usage details (a UFM that gives occ info for each free var of
+ -- the RHS) we can get the list of free vars -- or rather their Int keys --
+ -- by just extracting the keys from the finite map. Grimy, but fast.
+ -- Previously we had this:
+ -- [ bndr | bndr <- bndrs,
+ -- maybeToBool (lookupVarEnv rhs_usage bndr)]
+ -- which has n**2 cost, and this meant that edges_from alone
+ -- consumed 10% of total runtime!
+
+-----------------------------
+occAnalRec :: SCC (Node Details) -> (UsageDetails, [CoreBind])
+ -> (UsageDetails, [CoreBind])
+
+ -- The NonRec case is just like a Let (NonRec ...) above
+occAnalRec (AcyclicSCC (ND bndr rhs rhs_usage _, _, _)) (body_usage, binds)
+ | not (bndr `usedIn` body_usage)
+ = (body_usage, binds)
+
+ | otherwise -- It's mentioned in the body
+ = (body_usage' +++ addRuleUsage rhs_usage bndr, -- Note [Rules are extra RHSs]
+ NonRec tagged_bndr rhs : binds)
+ where
+ (body_usage', tagged_bndr) = tagBinder body_usage bndr
+
+
+ -- The Rec case is the interesting one
+ -- See Note [Loop breaking]
+occAnalRec (CyclicSCC nodes) (body_usage, binds)
+ | not (any (`usedIn` body_usage) bndrs) -- NB: look at body_usage, not total_usage
+ = (body_usage, binds) -- Dead code
+
+ | otherwise -- At this point we always build a single Rec
+ = (final_usage, Rec pairs : binds)
+
+ where
+ bndrs = [b | (ND b _ _ _, _, _) <- nodes]
+ bndr_set = mkVarSet bndrs
+
+ ----------------------------
+ -- Tag the binders with their occurrence info
+ total_usage = foldl add_usage body_usage nodes
+ add_usage body_usage (ND bndr _ rhs_usage _, _, _)
+ = body_usage +++ addRuleUsage rhs_usage bndr
+ (final_usage, tagged_nodes) = mapAccumL tag_node total_usage nodes
+
+ tag_node :: UsageDetails -> Node Details -> (UsageDetails, Node Details)
+ -- (a) Tag the binders in the details with occ info
+ -- (b) Mark the binder with "weak loop-breaker" OccInfo
+ -- saying "no preInlineUnconditionally" if it is used
+ -- in any rule (lhs or rhs) of the recursive group
+ -- See Note [Weak loop breakers]
+ tag_node usage (ND bndr rhs rhs_usage rhs_fvs, k, ks)
+ = (usage `delVarEnv` bndr, (ND bndr2 rhs rhs_usage rhs_fvs, k, ks))
+ where
+ bndr2 | bndr `elemVarSet` all_rule_fvs = makeLoopBreaker True bndr1
+ | otherwise = bndr1
+ bndr1 = setBinderOcc usage bndr
+ all_rule_fvs = bndr_set `intersectVarSet` foldr (unionVarSet . idRuleVars)
+ emptyVarSet bndrs
+
+ ----------------------------
+ -- Now reconstruct the cycle
+ pairs | no_rules = reOrderCycle tagged_nodes
+ | otherwise = concatMap reOrderRec (stronglyConnCompFromEdgedVerticesR loop_breaker_edges)
+
+ -- See Note [Choosing loop breakers] for looop_breaker_edges
+ loop_breaker_edges = map mk_node tagged_nodes
+ mk_node (details@(ND _ _ _ rhs_fvs), k, _) = (details, k, new_ks)
+ where
+ new_ks = keysUFM (extendFvs rule_fv_env rhs_fvs rhs_fvs)
+
+ ------------------------------------
+ rule_fv_env :: IdEnv IdSet -- Variables from this group mentioned in RHS of rules
+ -- Domain is *subset* of bound vars (others have no rule fvs)
+ rule_fv_env = rule_loop init_rule_fvs
+
+ no_rules = null init_rule_fvs
+ init_rule_fvs = [(b, rule_fvs)
+ | b <- bndrs
+ , let rule_fvs = idRuleRhsVars b `intersectVarSet` bndr_set
+ , not (isEmptyVarSet rule_fvs)]
+
+ rule_loop :: [(Id,IdSet)] -> IdEnv IdSet -- Finds fixpoint
+ rule_loop fv_list
+ | no_change = env
+ | otherwise = rule_loop new_fv_list
+ where
+ env = mkVarEnv init_rule_fvs
+ (no_change, new_fv_list) = mapAccumL bump True fv_list
+ bump no_change (b,fvs)
+ | new_fvs `subVarSet` fvs = (no_change, (b,fvs))
+ | otherwise = (False, (b,new_fvs `unionVarSet` fvs))
+ where
+ new_fvs = extendFvs env emptyVarSet fvs
+
+extendFvs :: IdEnv IdSet -> IdSet -> IdSet -> IdSet
+-- (extendFVs env fvs s) returns (fvs `union` env(s))
+extendFvs env fvs id_set
+ = foldUFM_Directly add fvs id_set
+ where
+ add uniq _ fvs
+ = case lookupVarEnv_Directly env uniq of
+ Just fvs' -> fvs' `unionVarSet` fvs
+ Nothing -> fvs