[m-dev.] for review: --dead-code
Zoltan Somogyi
zs at cs.mu.OZ.AU
Wed Jul 19 11:46:13 AEST 2000
For review by anyone, but I would like Fergus to look at the code of the
predicate dead_code__adjust_where_needed.
Add a new optimization, enabled by the option --dead-code. This optimization
removes goals whose outputs are not used at all, and moves goals whose outputs
are only used on some computation branches to the starts of those branches,
so they do not need to be executed on other branches.
Such deletions/movements are done only when the semantic switches and the
properties of the relevant goal together permit it.
compiler/dead_code.m:
A new module to perform the goal rearrangement.
compiler/hlds_goal.m:
The new optimization needs to know how many functors the switched-on
variable can be bound to, so it can check whether a given number of
switch arms covers all alternatives or not. To make access to this
information convenient, we add a field to the goal_path_step
alternative for switch arm entry that records this number.
compiler/goal_path.m:
Fill in this number.
To make this possible, we thread the necessary information through the
predicates in this module.
compiler/trace.m:
Ignore the new field when generating goal paths strings.
compiler/mercury_compile.m:
Invoke dead_code.m if required.
compiler/options.m:
Define the --dead-code option.
compiler/hlds_pred.m:
Add some utility predicates for use by dead_code.m.
compiler/unused_args.m:
Use the new utility predicates instead of reimplementing them.
Zoltan.
cvs diff: Diffing .
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/dead_code.m
===================================================================
RCS file: dead_code.m
diff -N dead_code.m
--- /dev/null Thu Mar 4 04:20:11 1999
+++ dead_code.m Wed Jul 19 11:33:38 2000
@@ -0,0 +1,1202 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2000 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% Author: zs.
+%
+% This module implements two related source-to-source transforms,
+% both of which focus on goals that produce some variables, where these
+% variables are not always required by the following computation.
+%
+% If there are no computation paths on which the variables produced by a goal
+% may be needed, then the first transform deletes that goal.
+%
+% If the variables produced by a goal may be needed on some but not all
+% computation paths, then the second transform moves that goal to the starts
+% of those computation paths, thus avoiding the cost of executing the goal
+% on all other computation paths. (This is related to the concept of partial
+% redundancy elimination (PRE) for imperative languages.)
+%
+% Mercury has two constructs that make it possible for a variable to be needed
+% on some computation paths but not others: switches and if-then-elses.
+%
+% In the case of switches, the alternative computation paths are those
+% corresponding to the possible values of the switched-on variable, and
+% not just the switch arms. Even if all switch arms need a variable, it
+% is an optimization to copy the code generating that variable to the starts of
+% all the switch arms if the switch is can_fail, i.e. there are some function
+% symbols that the switched-on variable can be bound to that do not have arms.
+%
+% In the case of if-then-elses, the alternatives are the then part and
+% the else part. Any variable needed by the condition is needed in both those
+% computation paths.
+%
+% From the point of view of this transform, disjunctions are not branched
+% control structures, because entering a disjunct does not preclude later
+% entering another disjunct. Any variable needed by any disjunct must therefore
+% be produced before control enters the disjunction. (In theory, a disjunct
+% that cannot fail in a model_semi disjunction prevents entry to the following
+% disjuncts, but any such following disjuncts will have been removed long ago
+% by simplification.)
+%
+% Note that by avoiding the execution of a goal that appears in the original
+% source code of the program, both these transforms can in general change the
+% operational semantics of the program. Therefore a goal can only be eliminated
+% or moved if the goal is has no observable effect except the result it
+% generates (i.e is pure, cannot fail, cannot loop, cannot raise an exception),
+% which is usually true only of goals composed entirely of builtins, or if
+% the semantics options explicitly permit the change in the operational
+% semantics, which will usually be an improvement (e.g. avoiding an infinite
+% loop or an unnecessary exception).
+%
+%-----------------------------------------------------------------------------%
+
+:- module dead_code.
+
+:- interface.
+
+:- import_module hlds_module, hlds_pred.
+:- import_module io.
+
+:- pred dead_code__process_proc_msg(pred_id::in, proc_id::in,
+ proc_info::in, proc_info::out, module_info::in, module_info::out,
+ io__state::di, io__state::uo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module prog_data, hlds_goal, prog_data.
+:- import_module inst_match, instmap, mode_util.
+:- import_module passes_aux, hlds_out, globals, options.
+:- import_module goal_path, quantification.
+:- import_module std_util, bool, int, list, assoc_list, map, set, require.
+
+ % The branch_alts and branch_point types record the information the
+ % transform needs to know about a particular branched control
+ % structure: where it is, what kind it is, and how many alternatives
+ % it has.
+
+:- type branch_point
+ ---> branch_point(
+ goal_path, % The position of the branch point.
+ branch_alts % What kind of goal the branch point
+ % is, and many branches it has.
+ % Note that the second argument is a
+ % function of the first.
+ ).
+
+:- type branch_alts
+ ---> ite % If-then-elses always have two
+ % alternatives: the then branch
+ % (numbered 1) and the else branch
+ % (numbered 2).
+
+ ; switch(int). % The number of alternatives in a
+ % switch is equal to the number of
+ % function symbols in the type of
+ % the switched-on variable; this number
+ % is given by the argument. If the
+ % switch cannot_fail, then this will be
+ % equal to the number of cases;
+ % if the switch can_fail, there will be
+ % strictly fewer cases than this.
+
+ % The location type identifies one arm of a branched control structure.
+ % The branched control structure id is a branch_point instead of a
+ % simple goal_path because without the branch_alts info, the
+ % transformation cannot tell if a given set of branches of a branched
+ % control structure covers all possible execution paths or not.
+
+:- type location
+ ---> location(
+ branch_point, % To which branched control structure
+ % does the location belong.
+ int % The branch within that control
+ % structure.
+ ).
+
+ % The where_needed_map type maps each variable to the set of
+ % computation branches where it is needed. If a variable is needed
+ % everywhere, then the computation producing it cannot be eliminated
+ % or moved. If it is not needed at all, its producer can be eliminated.
+ % If it is needed on some but not all branches, then the producer
+ % can be moved to the starts of those branches.
+ %
+ % The set of branches to whose starts the producer can be moved
+ % is represented as a map from the id of the branched control
+ % structure to the set of branch numbers within that branched control
+ % structure. If the branched control structure at goal path gp is
+ % mapped to a set including N, then the producer of that variable
+ % may be moved to the start of the goal with goal path <gp>;sN;
+ % (if the control structure is a switch) or <gp>;t; or <gp>;e;
+ % (if the control structure is an if-then-else).
+ %
+ % Since <gp>;sN; is conjoined with e.g. <gp>;sN;<gp2>;sM;
+ % it would be a mode error (variable having two conjoined producers)
+ % for the transformed code to have the producer of some variable
+ % inserted at the start of both those goals. It is therefore an
+ % invariant that a where_needed structure mapping gp to N
+ % will not contain any keys whose goal_path includes <gp>;sN;
+ % or its if-then-else equivalent.
+ %
+ % An example:
+ %
+ % % switch on X at goal path gp
+ % ( % s1
+ % X = a,
+ % ... code that needs Y and Z ...
+ % ; % s2
+ % X = b,
+ % ( Y = f ->
+ % ... code that needs only Z ...
+ % ;
+ % ... code that does not need Y or Z ...
+ % )
+ % )
+ %
+ % X is needed everywhere, since even if X is bound to c, its value must
+ % be tested.
+ %
+ % Y is needed everywhere iff the type of X contains only a and b,
+ % otherwise it is needed only in the <gp>;s1; and <gp>;s2; switch arms.
+ %
+ % Z is needed in <gp>;s1; and <gp>;s2;t; but is not needed in the
+ % <gp>;s2;e; else arm. Therefore the where_needed_branches map for Z
+ % will map gp to 1 and <gp>;s2; to 1.
+
+:- type where_needed_map == map(prog_var, where_needed).
+
+:- type where_needed
+ ---> everywhere
+ ; branches(where_needed_branches).
+
+:- type where_needed_branches == map(branch_point, set(int)).
+
+ % The refined_goal_map structure maps branch goals to the list of
+ % producers that should be moved to the start of that branch.
+ % The order is important, since some of the producers in such a list
+ % may depend on variables produced by other goals that precede them
+ % in the list.
+
+:- type refined_goal_map == map(pair(goal_path, int), list(hlds_goal)).
+
+%-----------------------------------------------------------------------------%
+
+% The transformation considers every nonlocal variable of a goal
+% that is bound on entry to be consumed by that goal. If the nonlocal set
+% contains any such variables that are not actually needed by the goal,
+% then the transformation will not be as effective as it could be.
+% Therefore we preprocess the procedure body to ensure that the nonlocals
+% sets are accurate reflections of the true needs of goals.
+
+dead_code__process_proc_msg(PredId, ProcId, ProcInfo0, ProcInfo,
+ ModuleInfo0, ModuleInfo) -->
+ globals__io_lookup_bool_option(very_verbose, VeryVerbose),
+ globals__io_lookup_int_option(vn_fudge, Levels),
+ ( { VeryVerbose = yes } ->
+ io__write_string("% Removing dead code in "),
+ hlds_out__write_pred_proc_id(ModuleInfo, PredId, ProcId),
+ io__write_string(": "),
+ { dead_code__pre_process_proc(ProcInfo0, ProcInfo1) },
+ { dead_code__process_proc(ProcInfo1, ProcInfo,
+ ModuleInfo0, ModuleInfo, Levels, Successful) },
+ (
+ { Successful = yes },
+ io__write_string("done.\n")
+ ;
+ { Successful = no },
+ io__write_string("none found.\n")
+ )
+ ;
+ { dead_code__pre_process_proc(ProcInfo0, ProcInfo1) },
+ { dead_code__process_proc(ProcInfo1, ProcInfo,
+ ModuleInfo0, ModuleInfo, Levels, _) }
+ ).
+
+:- pred dead_code__pre_process_proc(proc_info::in, proc_info::out) is det.
+
+dead_code__pre_process_proc(ProcInfo0, ProcInfo) :-
+ proc_info_headvars(ProcInfo0, HeadVars),
+ proc_info_goal(ProcInfo0, Goal0),
+ proc_info_varset(ProcInfo0, Varset0),
+ proc_info_vartypes(ProcInfo0, VarTypes0),
+ implicitly_quantify_clause_body(HeadVars, Goal0,
+ Varset0, VarTypes0, Goal, Varset, VarTypes, _Warnings),
+ proc_info_set_goal(ProcInfo0, Goal, ProcInfo1),
+ proc_info_set_varset(ProcInfo1, Varset, ProcInfo2),
+ proc_info_set_vartypes(ProcInfo2, VarTypes, ProcInfo).
+
+% The source-to-source transform operates in two phases.
+%
+% The first phase traverses the procedure body, keeping track of which
+% variables are needed where. When it finds a goal that can be deleted,
+% it deletes it by replacing it with the goal `true' (i.e. conj([])).
+% When it finds a goal that can be moved, it does the same, but also
+% records in the RefinedGoalsMap that the deleted goal must later be
+% inserted at the starts of the branches where its outputs may be needed,
+% and accordingly notes that its own inputs are needed in those branches.
+%
+% The second phase traverses the modified problem body, and inserts the
+% goals in the RefinedGoalsMap at the starts of the indicated branches.
+% This phase identified the indicated branches by the goal_path annotations
+% on their parents. These may be out of date since the first phase will have
+% deleted some goals, but since neither phase modifies the goal_path annotation
+% on a goal once that goal has been inserted into the RefinedGoalsMap,
+% this does not matter.
+%
+% Neither phase traverses the internals of a goal that has been moved.
+% To make sure that such goals are optimized whenever possible, the algorithm
+% invokes itself recursively whenever it was able to successfully (delete or)
+% move a goal. This cannot lead to infinite recursion, since each iteration
+% will strictly reduce the number of computation paths on which a subgoal
+% of the procedure body is executed. Since both the number of subgoals and
+% computation paths are finite, the recursion must end.
+
+:- pred dead_code__process_proc(proc_info::in, proc_info::out,
+ module_info::in, module_info::out, int::in, bool::out) is det.
+
+dead_code__process_proc(ProcInfo0, ProcInfo, ModuleInfo0, ModuleInfo,
+ Levels, Successful) :-
+ goal_path__fill_slots(ProcInfo0, ModuleInfo0, ProcInfo1),
+ proc_info_goal(ProcInfo1, Goal0),
+ proc_info_varset(ProcInfo1, Varset0),
+ proc_info_vartypes(ProcInfo1, VarTypes0),
+ proc_info_get_initial_instmap(ProcInfo1, ModuleInfo0, InstMap0),
+ Goal0 = _ - GoalInfo0,
+ goal_info_get_instmap_delta(GoalInfo0, InstMapDelta),
+ instmap__apply_instmap_delta(InstMap0, InstMapDelta, InstMap),
+ proc_info_changed_inst_head_vars(ModuleInfo0, ProcInfo1,
+ NeededVarsList),
+ map__init(WhereNeededMap0),
+ NeededEverywhere =
+ lambda([Var::in, NeededMap0::in, NeededMap::out] is det, (
+ map__det_insert(NeededMap0, Var, everywhere, NeededMap)
+ )),
+ list__foldl(NeededEverywhere, NeededVarsList,
+ WhereNeededMap0, WhereNeededMap1),
+ map__init(RefinedGoals0),
+ module_info_globals(ModuleInfo0, Globals),
+ globals__lookup_bool_option(Globals, reorder_conj, ReorderConj),
+ globals__lookup_bool_option(Globals, fully_strict, FullyStrict),
+ (
+ ( ReorderConj = yes
+ ; FullyStrict = yes
+ )
+ ->
+ MoveAny = no
+ ;
+ MoveAny = yes
+ ),
+ dead_code__process_goal(Goal0, Goal1, InstMap0, InstMap, ModuleInfo0,
+ MoveAny, WhereNeededMap1, _, RefinedGoals0, RefinedGoals1,
+ no, Changed),
+ dead_code__refine_goal(Goal1, RefinedGoals1, Goal2, RefinedGoals),
+ require(map__is_empty(RefinedGoals),
+ "dead_code__process_proc: goal reattachment unsuccessful"),
+ ( Changed = yes ->
+ % We need to fix up the goal_info by recalculating
+ % the nonlocal vars and the non-atomic instmap deltas.
+ proc_info_headvars(ProcInfo0, HeadVars),
+ implicitly_quantify_clause_body(HeadVars, Goal2,
+ Varset0, VarTypes0, Goal3, Varset, VarTypes, _Warnings),
+ recompute_instmap_delta(no, Goal3, Goal, VarTypes, InstMap0,
+ ModuleInfo0, ModuleInfo1),
+ proc_info_set_goal(ProcInfo1, Goal, ProcInfo2),
+ proc_info_set_varset(ProcInfo2, Varset, ProcInfo3),
+ proc_info_set_vartypes(ProcInfo3, VarTypes, ProcInfo4),
+ ( Levels > 1 ->
+ dead_code__process_proc(ProcInfo4, ProcInfo,
+ ModuleInfo1, ModuleInfo, Levels - 1, _)
+ ;
+ ProcInfo = ProcInfo4,
+ ModuleInfo = ModuleInfo1
+ ),
+ Successful = yes
+ ;
+ ProcInfo = ProcInfo0,
+ ModuleInfo = ModuleInfo0,
+ Successful = no
+ ).
+
+:- pred dead_code__process_goal(hlds_goal::in, hlds_goal::out,
+ instmap::in, instmap::in, module_info::in, bool::in,
+ where_needed_map::in, where_needed_map::out,
+ refined_goal_map::in, refined_goal_map::out,
+ bool::in, bool::out) is det.
+
+dead_code__process_goal(Goal0, Goal, InstMap0, InstMap, ModuleInfo, MoveAny,
+ WhereNeededMap0, WhereNeededMap, RefinedGoals0, RefinedGoals,
+ Changed0, Changed) :-
+ dead_code__can_eliminate_or_move(Goal0, InstMap0, InstMap, ModuleInfo,
+ MoveAny, WhereNeededMap0, WhereInfo),
+ (
+ WhereInfo = everywhere,
+ dead_code__process_goal_internal(Goal0, Goal,
+ InstMap0, InstMap, ModuleInfo, MoveAny,
+ WhereNeededMap0, WhereNeededMap1,
+ RefinedGoals0, RefinedGoals, Changed0, Changed)
+ ;
+ WhereInfo = branches(Branches),
+ dead_code__demand_inputs(Goal0, ModuleInfo, InstMap0,
+ WhereInfo, WhereNeededMap0, WhereNeededMap1),
+ map__to_assoc_list(Branches, BranchList),
+ list__foldl(dead_code__insert_branch_into_refined_goals(Goal0),
+ BranchList, RefinedGoals0, RefinedGoals),
+ true_goal(Goal),
+ Changed = yes
+ ),
+ dead_code__undemand_virgin_outputs(Goal0, ModuleInfo, InstMap0,
+ WhereNeededMap1, WhereNeededMap).
+
+:- pred dead_code__insert_branch_into_refined_goals(hlds_goal::in,
+ pair(branch_point, set(int))::in,
+ refined_goal_map::in, refined_goal_map::out) is det.
+
+dead_code__insert_branch_into_refined_goals(Goal, BranchPoint - BranchNumSet,
+ RefinedGoals0, RefinedGoals) :-
+ BranchPoint = branch_point(GoalPath, _),
+ set__to_sorted_list(BranchNumSet, BranchNums),
+ list__foldl(dead_code__insert_branch_arm_into_refined_goals(
+ Goal, GoalPath), BranchNums, RefinedGoals0, RefinedGoals).
+
+:- pred dead_code__insert_branch_arm_into_refined_goals(hlds_goal::in,
+ goal_path::in, int::in,
+ refined_goal_map::in, refined_goal_map::out) is det.
+
+dead_code__insert_branch_arm_into_refined_goals(Goal, GoalPath, BranchNum,
+ RefinedGoals0, RefinedGoals) :-
+ Key = GoalPath - BranchNum,
+ ( map__search(RefinedGoals0, Key, Goals0) ->
+ Goals = [Goal | Goals0],
+ map__det_update(RefinedGoals0, Key, Goals, RefinedGoals)
+ ;
+ map__det_insert(RefinedGoals0, Key, [Goal], RefinedGoals)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+:- pred dead_code__can_eliminate_or_move(hlds_goal::in,
+ instmap::in, instmap::in, module_info::in, bool::in,
+ where_needed_map::in, where_needed::out) is det.
+
+dead_code__can_eliminate_or_move(Goal, InstMap0, InstMap, ModuleInfo, MoveAny,
+ WhereNeededMap, WhereInfo) :-
+ instmap_changed_vars(InstMap0, InstMap, ModuleInfo, ChangedVarSet),
+ set__to_sorted_list(ChangedVarSet, ChangedVars),
+ map__init(Empty),
+ WhereInfo0 = branches(Empty),
+ Goal = _ - GoalInfo,
+ goal_info_get_goal_path(GoalInfo, CurrentPath),
+ list__foldl(
+ dead_code__collect_where_needed(CurrentPath, WhereNeededMap),
+ ChangedVars, WhereInfo0, WhereInfo1),
+ dead_code__adjust_where_needed(Goal, MoveAny, WhereInfo1, WhereInfo).
+
+:- pred dead_code__collect_where_needed(goal_path::in, where_needed_map::in,
+ prog_var::in, where_needed::in, where_needed::out) is det.
+
+dead_code__collect_where_needed(CurrentPath, WhereNeededMap, ChangedVar,
+ WhereInfo0, WhereInfo) :-
+ ( map__search(WhereNeededMap, ChangedVar, Where) ->
+ dead_code__where_needed_upper_bound(CurrentPath,
+ Where, WhereInfo0, WhereInfo)
+ ;
+ WhereInfo = WhereInfo0
+ ).
+
+% This is the predicate responsible for ensuring that the act of optimizing
+% away the execution of a goal on some or all computation paths changes the
+% operational semantics only in ways that are explicitly permitted by the
+% programmer.
+
+:- pred dead_code__adjust_where_needed(hlds_goal::in, bool::in,
+ where_needed::in, where_needed::out) is det.
+
+dead_code__adjust_where_needed(Goal, MoveAny, WhereInfo0, WhereInfo) :-
+ (
+ Goal = GoalExpr - GoalInfo,
+ (
+ % Do not move goals that can fail, since
+ % doing so can cause execution to reach goals
+ % it shouldn't, and those goals may have
+ % undesirable behavior (e.g. infinite loops).
+ goal_info_get_determinism(GoalInfo, Detism),
+ dead_code__detism_is_moveable(Detism, no)
+ ;
+ % Do not move impure or semipure goals,
+ % since their ordering wrt other such goals
+ % must be preserved.
+ goal_info_get_features(GoalInfo, Features),
+ ( set__member((impure), Features)
+ ; set__member((semipure), Features)
+ )
+ ;
+ % If we are required to preserve the
+ % operational semantics of the original
+ % program exactly, move only goals whose
+ % movement cannot affect the operational
+ % semantics.
+ MoveAny = no,
+ \+ dead_code__cannot_diverge(Goal)
+ ;
+ % Do not delete the `true' goal, since
+ % deleting it is a no-op, and thus does *not*
+ % strictly reduce the number of computation
+ % paths on which a subgoal of the procedure
+ % body is executed.
+ GoalExpr = conj([])
+ )
+ % Later we may also want to add space time tradeoffs.
+ % E.g. if profiling shows that Goal is required in
+ % 10 branches that account for 99% of all executions
+ % and is not required in 5 branches that account for
+ % the remaining 1%, and Goal itself is sufficiently
+ % cheap to execute, then not moving Goal may cost
+ % a small slowdown in 1% of cases but avoid 9 extra
+ % copies of Goal. Due to better instruction cache
+ % behavior, not moving Goal may in fact yield faster
+ % code after all.
+ ->
+ WhereInfo = everywhere
+ ;
+ WhereInfo = WhereInfo0
+ ).
+
+:- pred dead_code__detism_is_moveable(determinism::in, bool::out) is det.
+
+dead_code__detism_is_moveable(det, yes).
+dead_code__detism_is_moveable(semidet, no).
+dead_code__detism_is_moveable(nondet, no).
+dead_code__detism_is_moveable(multidet, yes).
+dead_code__detism_is_moveable(erroneous, no).
+dead_code__detism_is_moveable(failure, no).
+dead_code__detism_is_moveable(cc_nondet, no).
+dead_code__detism_is_moveable(cc_multidet, yes).
+
+:- pred dead_code__cannot_diverge(hlds_goal::in) is semidet.
+
+dead_code__cannot_diverge(unify(_, _, _, _, _) - _).
+dead_code__cannot_diverge(conj(Goals) - _) :-
+ % list__all_true
+ list__takewhile(dead_code__cannot_diverge, Goals, _, []).
+dead_code__cannot_diverge(disj(Goals, _) - _) :-
+ % list__all_true
+ list__takewhile(dead_code__cannot_diverge, Goals, _, []).
+dead_code__cannot_diverge(switch(_, _, Cases, _) - _) :-
+ % list__all_true
+ list__takewhile(dead_code__cannot_diverge_case, Cases, _, []).
+dead_code__cannot_diverge(if_then_else(_, Cond, Then, Else, _) - _) :-
+ dead_code__cannot_diverge(Cond),
+ dead_code__cannot_diverge(Then),
+ dead_code__cannot_diverge(Else).
+
+:- pred dead_code__cannot_diverge_case(case::in) is semidet.
+
+dead_code__cannot_diverge_case(case(_, Goal)) :-
+ dead_code__cannot_diverge(Goal).
+
+%---------------------------------------------------------------------------%
+
+:- pred dead_code__demand_inputs(hlds_goal::in, module_info::in, instmap::in,
+ where_needed::in, where_needed_map::in, where_needed_map::out) is det.
+
+dead_code__demand_inputs(Goal, ModuleInfo, InstMap0, WhereNeeded,
+ WhereNeededMap0, WhereNeededMap) :-
+ Goal = _ - GoalInfo,
+ goal_info_get_nonlocals(GoalInfo, NonLocalSet),
+ goal_info_get_goal_path(GoalInfo, GoalPath),
+ set__to_sorted_list(NonLocalSet, NonLocals),
+ list__filter(dead_code__nonlocal_may_be_input(ModuleInfo, InstMap0),
+ NonLocals, Inputs),
+ list__foldl(dead_code__demand_var(GoalPath, WhereNeeded), Inputs,
+ WhereNeededMap0, WhereNeededMap).
+
+:- pred dead_code__nonlocal_may_be_input(module_info::in, instmap::in,
+ prog_var::in) is semidet.
+
+dead_code__nonlocal_may_be_input(ModuleInfo, InstMap0, Var) :-
+ instmap__lookup_var(InstMap0, Var, Inst),
+ inst_is_bound(ModuleInfo, Inst).
+
+%---------------------------------------------------------------------------%
+
+:- pred dead_code__undemand_virgin_outputs(hlds_goal::in, module_info::in,
+ instmap::in, where_needed_map::in, where_needed_map::out) is det.
+
+dead_code__undemand_virgin_outputs(Goal, ModuleInfo, InstMap0,
+ WhereNeededMap0, WhereNeededMap) :-
+ Goal = _ - GoalInfo,
+ goal_info_get_nonlocals(GoalInfo, NonLocalSet),
+ set__to_sorted_list(NonLocalSet, NonLocals),
+ list__filter(dead_code__nonlocal_is_virgin_output(ModuleInfo, InstMap0),
+ NonLocals, VirginOutputs),
+ list__foldl(dead_code__undemand_var, VirginOutputs,
+ WhereNeededMap0, WhereNeededMap).
+
+:- pred dead_code__nonlocal_is_virgin_output(module_info::in, instmap::in,
+ prog_var::in) is semidet.
+
+dead_code__nonlocal_is_virgin_output(ModuleInfo, InstMap0, Var) :-
+ instmap__lookup_var(InstMap0, Var, Inst),
+ \+ inst_is_bound(ModuleInfo, Inst).
+
+%---------------------------------------------------------------------------%
+
+:- pred dead_code__demand_var(goal_path::in, where_needed::in, prog_var::in,
+ where_needed_map::in, where_needed_map::out) is det.
+
+dead_code__demand_var(CurrentPath, WhereNeeded, Var,
+ WhereNeededMap0, WhereNeededMap) :-
+ ( map__search(WhereNeededMap0, Var, Where0) ->
+ dead_code__where_needed_upper_bound(CurrentPath,
+ WhereNeeded, Where0, Where),
+ map__det_update(WhereNeededMap0, Var, Where, WhereNeededMap)
+ ;
+ map__det_insert(WhereNeededMap0, Var, WhereNeeded,
+ WhereNeededMap)
+ ).
+
+:- pred dead_code__undemand_var(prog_var::in,
+ where_needed_map::in, where_needed_map::out) is det.
+
+dead_code__undemand_var(Var, WhereNeededMap0, WhereNeededMap) :-
+ map__delete(WhereNeededMap0, Var, WhereNeededMap).
+
+%---------------------------------------------------------------------------%
+
+:- pred dead_code__demand_var_everywhere(prog_var::in, where_needed::in,
+ where_needed::out) is det.
+
+dead_code__demand_var_everywhere(_Var, _WhereNeeded0, everywhere).
+
+%---------------------------------------------------------------------------%
+
+:- pred dead_code__process_goal_internal(hlds_goal::in, hlds_goal::out,
+ instmap::in, instmap::in, module_info::in, bool::in,
+ where_needed_map::in, where_needed_map::out,
+ refined_goal_map::in, refined_goal_map::out,
+ bool::in, bool::out) is det.
+
+dead_code__process_goal_internal(Goal0, Goal, InstMap0, InstMap, ModuleInfo,
+ MoveAny, WhereNeededMap0, WhereNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed) :-
+ Goal0 = GoalExpr0 - GoalInfo0,
+ % Goal = GoalExpr - GoalInfo,
+ (
+ GoalExpr0 = unify(_, _, _, _, _),
+ Goal = Goal0,
+ dead_code__demand_inputs(Goal, ModuleInfo, InstMap0,
+ everywhere, WhereNeededMap0, WhereNeededMap),
+ RefinedGoals = RefinedGoals0,
+ Changed = Changed0
+ ;
+ GoalExpr0 = call(_, _, _, _, _, _),
+ Goal = Goal0,
+ dead_code__demand_inputs(Goal, ModuleInfo, InstMap0,
+ everywhere, WhereNeededMap0, WhereNeededMap),
+ RefinedGoals = RefinedGoals0,
+ Changed = Changed0
+ ;
+ GoalExpr0 = generic_call(_, _, _, _),
+ Goal = Goal0,
+ dead_code__demand_inputs(Goal, ModuleInfo, InstMap0,
+ everywhere, WhereNeededMap0, WhereNeededMap),
+ RefinedGoals = RefinedGoals0,
+ Changed = Changed0
+ ;
+ GoalExpr0 = pragma_c_code(_, _, _, _, _, _, _),
+ Goal = Goal0,
+ dead_code__demand_inputs(Goal, ModuleInfo, InstMap0,
+ everywhere, WhereNeededMap0, WhereNeededMap),
+ RefinedGoals = RefinedGoals0,
+ Changed = Changed0
+ ;
+ GoalExpr0 = par_conj(_, _),
+ Goal = Goal0,
+ dead_code__demand_inputs(Goal, ModuleInfo, InstMap0,
+ everywhere, WhereNeededMap0, WhereNeededMap),
+ RefinedGoals = RefinedGoals0,
+ Changed = Changed0
+ ;
+ GoalExpr0 = conj(Conjuncts0),
+ dead_code__process_conj(Conjuncts0, Conjuncts,
+ InstMap0, InstMap, ModuleInfo, MoveAny,
+ WhereNeededMap0, WhereNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed),
+ GoalExpr = conj(Conjuncts),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = switch(SwitchVar, CanFail, Cases0, StoreMap),
+ (
+ Cases0 = [case(_, _ - FirstCaseGoalInfo) | _],
+ goal_info_get_goal_path(FirstCaseGoalInfo,
+ FirstCaseGoalPath),
+ FirstCaseGoalPath = [SwitchStep | _],
+ SwitchStep = switch(_, NumCases)
+ ->
+ NumAlt = NumCases
+ ;
+ error("dead_code__process_goal_internal: switch count")
+ ),
+ goal_info_get_goal_path(GoalInfo0, GoalPath),
+ BranchPoint = branch_point(GoalPath, switch(NumAlt)),
+ map__map_values(dead_code__demand_var_everywhere,
+ WhereNeededMap0, WhereNeededMap1),
+ map__init(BranchNeededMap0),
+ dead_code__process_cases(Cases0, BranchPoint, 1,
+ InstMap0, InstMap, ModuleInfo, MoveAny,
+ GoalPath, Cases, WhereNeededMap1,
+ BranchNeededMap0, BranchNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed),
+ dead_code__merge_where_needed_maps(GoalPath,
+ WhereNeededMap1, BranchNeededMap, WhereNeededMap2),
+ dead_code__demand_var(GoalPath, everywhere, SwitchVar,
+ WhereNeededMap2, WhereNeededMap),
+ GoalExpr = switch(SwitchVar, CanFail, Cases, StoreMap),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = disj(Disjuncts0, StoreMap),
+ goal_info_get_goal_path(GoalInfo0, GoalPath),
+ map__map_values(dead_code__demand_var_everywhere,
+ WhereNeededMap0, WhereNeededMap1),
+ dead_code__process_disj(Disjuncts0, InstMap0, InstMap,
+ ModuleInfo, MoveAny, GoalPath, Disjuncts,
+ WhereNeededMap1, WhereNeededMap1, WhereNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed),
+ GoalExpr = disj(Disjuncts, StoreMap),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = if_then_else(Quant, Cond0, Then0, Else0, StoreMap),
+ goal_info_get_goal_path(GoalInfo0, GoalPath),
+ BranchPoint = branch_point(GoalPath, ite),
+ map__map_values(dead_code__demand_var_everywhere,
+ WhereNeededMap0, WhereNeededMap1),
+ dead_code__process_ite(Cond0, Then0, Else0, BranchPoint,
+ InstMap0, InstMap, ModuleInfo, MoveAny, GoalPath,
+ Cond, Then, Else, WhereNeededMap1, WhereNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed),
+ GoalExpr = if_then_else(Quant, Cond, Then, Else, StoreMap),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = not(NegGoal0),
+ dead_code__process_goal(NegGoal0, NegGoal, InstMap0, InstMap,
+ ModuleInfo, MoveAny, WhereNeededMap0, WhereNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed),
+ GoalExpr = not(NegGoal),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = some(Vars, CanRemove, SomeGoal0),
+ dead_code__process_goal(SomeGoal0, SomeGoal, InstMap0, InstMap,
+ ModuleInfo, MoveAny, WhereNeededMap0, WhereNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed),
+ GoalExpr = some(Vars, CanRemove, SomeGoal),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = bi_implication(_, _),
+ error("bi-implication in dead_code__process_goal_internal")
+ ).
+
+%---------------------------------------------------------------------------%
+
+:- type bracketed_goal
+ ---> bracketed_goal(hlds_goal, instmap, instmap).
+
+:- pred dead_code__process_conj(list(hlds_goal)::in, list(hlds_goal)::out,
+ instmap::in, instmap::in, module_info::in, bool::in,
+ where_needed_map::in, where_needed_map::out,
+ refined_goal_map::in, refined_goal_map::out,
+ bool::in, bool::out) is det.
+
+dead_code__process_conj(Goals0, Goals, InstMap0, _InstMap, ModuleInfo, MoveAny,
+ WhereNeededMap0, WhereNeededMap, RefinedGoals0, RefinedGoals,
+ Changed0, Changed) :-
+ dead_code__build_bracketed_conj(Goals0, InstMap0, BracketedGoals),
+ list__reverse(BracketedGoals, RevBracketedGoals),
+ dead_code__process_rev_bracketed_conj(RevBracketedGoals, RevGoals,
+ ModuleInfo, MoveAny, WhereNeededMap0, WhereNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed),
+ list__reverse(RevGoals, Goals).
+
+:- pred dead_code__build_bracketed_conj(list(hlds_goal)::in, instmap::in,
+ list(bracketed_goal)::out) is det.
+
+dead_code__build_bracketed_conj([], _, []).
+dead_code__build_bracketed_conj([Goal | Goals], InstMap0, BracketedGoals) :-
+ ( instmap__is_unreachable(InstMap0) ->
+ BracketedGoals = []
+ ;
+ Goal = _ - GoalInfo,
+ goal_info_get_instmap_delta(GoalInfo, InstMapDelta),
+ instmap__apply_instmap_delta(InstMap0, InstMapDelta, InstMap1),
+ dead_code__build_bracketed_conj(Goals, InstMap1,
+ BracketedTail),
+ BracketedGoal = bracketed_goal(Goal, InstMap0, InstMap1),
+ BracketedGoals = [BracketedGoal | BracketedTail]
+ ).
+
+:- pred dead_code__process_rev_bracketed_conj(list(bracketed_goal)::in,
+ list(hlds_goal)::out, module_info::in, bool::in,
+ where_needed_map::in, where_needed_map::out,
+ refined_goal_map::in, refined_goal_map::out,
+ bool::in, bool::out) is det.
+
+dead_code__process_rev_bracketed_conj([], [], _, _,
+ WhereNeededMap, WhereNeededMap,
+ RefinedGoals, RefinedGoals, Changed, Changed).
+dead_code__process_rev_bracketed_conj([BracketedGoal | BracketedGoals],
+ Goals, ModuleInfo, MoveAny, WhereNeededMap0, WhereNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed) :-
+ BracketedGoal = bracketed_goal(Goal0, InstMap0, InstMap),
+ dead_code__process_goal(Goal0, Goal1, InstMap0, InstMap, ModuleInfo,
+ MoveAny, WhereNeededMap0, WhereNeededMap1,
+ RefinedGoals0, RefinedGoals1, Changed0, Changed1),
+ dead_code__process_rev_bracketed_conj(BracketedGoals,
+ Goals1, ModuleInfo, MoveAny, WhereNeededMap1, WhereNeededMap,
+ RefinedGoals1, RefinedGoals, Changed1, Changed),
+ ( true_goal(Goal1) ->
+ Goals = Goals1
+ ;
+ Goals = [Goal1 | Goals1]
+ ).
+
+%---------------------------------------------------------------------------%
+
+:- pred dead_code__process_disj(list(hlds_goal)::in, instmap::in, instmap::in,
+ module_info::in, bool::in, goal_path::in, list(hlds_goal)::out,
+ where_needed_map::in, where_needed_map::in, where_needed_map::out,
+ refined_goal_map::in, refined_goal_map::out,
+ bool::in, bool::out) is det.
+
+dead_code__process_disj([], _, _, _, _, _, [],
+ _, WhereNeededMap, WhereNeededMap,
+ RefinedGoals, RefinedGoals, Changed, Changed).
+dead_code__process_disj([Goal0 | Goals0], InstMap0, InstMap, ModuleInfo,
+ MoveAny, CurrentPath, [Goal | Goals], StartWhereNeededMap,
+ WhereNeededMap0, WhereNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed) :-
+ dead_code__process_goal(Goal0, Goal, InstMap0, InstMap, ModuleInfo,
+ MoveAny, StartWhereNeededMap, WhereNeededMapFirst,
+ RefinedGoals0, RefinedGoals1, Changed0, Changed1),
+ map__to_assoc_list(WhereNeededMapFirst, WhereNeededList),
+ dead_code__add_where_needed_list(WhereNeededList, CurrentPath,
+ WhereNeededMap0, WhereNeededMap1),
+ dead_code__process_disj(Goals0, InstMap0, InstMap, ModuleInfo,
+ MoveAny, CurrentPath, Goals,
+ StartWhereNeededMap, WhereNeededMap1, WhereNeededMap,
+ RefinedGoals1, RefinedGoals, Changed1, Changed).
+
+%---------------------------------------------------------------------------%
+
+:- pred dead_code__process_cases(list(case)::in, branch_point::in, int::in,
+ instmap::in, instmap::in, module_info::in, bool::in, goal_path::in,
+ list(case)::out, where_needed_map::in,
+ where_needed_map::in, where_needed_map::out,
+ refined_goal_map::in, refined_goal_map::out,
+ bool::in, bool::out) is det.
+
+dead_code__process_cases([], _, _, _, _, _, _, _, [],
+ _, WhereNeededMap, WhereNeededMap,
+ RefinedGoals, RefinedGoals, Changed, Changed).
+dead_code__process_cases([case(Var, Goal0) | Cases0], BranchPoint, BranchNum,
+ InstMap0, InstMap, ModuleInfo, MoveAny, CurrentPath,
+ [case(Var, Goal) | Cases], StartWhereNeededMap,
+ WhereNeededMap0, WhereNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed) :-
+ dead_code__process_goal(Goal0, Goal, InstMap0, InstMap, ModuleInfo,
+ MoveAny, StartWhereNeededMap, WhereNeededMapFirst,
+ RefinedGoals0, RefinedGoals1, Changed0, Changed1),
+ map__to_assoc_list(WhereNeededMapFirst, WhereNeededList),
+ dead_code__add_alt_start(WhereNeededList, BranchPoint, BranchNum,
+ CurrentPath, WhereNeededMap0, WhereNeededMap1),
+ dead_code__process_cases(Cases0, BranchPoint, BranchNum + 1,
+ InstMap0, InstMap, ModuleInfo, MoveAny, CurrentPath, Cases,
+ StartWhereNeededMap, WhereNeededMap1, WhereNeededMap,
+ RefinedGoals1, RefinedGoals, Changed1, Changed).
+
+%---------------------------------------------------------------------------%
+
+:- pred dead_code__process_ite(hlds_goal::in, hlds_goal::in, hlds_goal::in,
+ branch_point::in, instmap::in, instmap::in, module_info::in, bool::in,
+ goal_path::in, hlds_goal::out, hlds_goal::out, hlds_goal::out,
+ where_needed_map::in, where_needed_map::out,
+ refined_goal_map::in, refined_goal_map::out,
+ bool::in, bool::out) is det.
+
+dead_code__process_ite(Cond0, Then0, Else0, BranchPoint,
+ InstMap0, InstMap, ModuleInfo, MoveAny, CurrentPath,
+ Cond, Then, Else, WhereNeededMap0, WhereNeededMap,
+ RefinedGoals0, RefinedGoals, Changed0, Changed) :-
+ Cond0 = _ - CondInfo0,
+ goal_info_get_instmap_delta(CondInfo0, InstMapDelta),
+ instmap__apply_instmap_delta(InstMap0, InstMapDelta, InstMapCond),
+
+ dead_code__process_goal(Else0, Else, InstMap0, InstMap, ModuleInfo,
+ MoveAny, WhereNeededMap0, WhereNeededMapElse,
+ RefinedGoals0, RefinedGoals1, Changed0, Changed1),
+ dead_code__process_goal(Then0, Then, InstMapCond, InstMap, ModuleInfo,
+ MoveAny, WhereNeededMap0, WhereNeededMapThen,
+ RefinedGoals1, RefinedGoals2, Changed1, Changed2),
+
+ map__init(BranchNeededMap0),
+ map__to_assoc_list(WhereNeededMapElse, WhereNeededListElse),
+ dead_code__add_alt_start(WhereNeededListElse, BranchPoint, 2,
+ CurrentPath, BranchNeededMap0, BranchNeededMap1),
+ map__to_assoc_list(WhereNeededMapThen, WhereNeededListThen),
+ dead_code__add_alt_start(WhereNeededListThen, BranchPoint, 1,
+ CurrentPath, BranchNeededMap1, BranchNeededMap),
+ dead_code__merge_where_needed_maps(CurrentPath,
+ WhereNeededMap0, BranchNeededMap, WhereNeededMapCond),
+
+ dead_code__process_goal(Cond0, Cond, InstMap0, InstMapCond, ModuleInfo,
+ MoveAny, WhereNeededMapCond, WhereNeededMap,
+ RefinedGoals2, RefinedGoals, Changed2, Changed).
+
+%---------------------------------------------------------------------------%
+
+% Merge two where_needed_maps, so that if var V is needed at branch B
+% in the resulting where_needed_map iff it is needed there in one of the input
+% maps.
+
+:- pred dead_code__merge_where_needed_maps(goal_path::in,
+ where_needed_map::in, where_needed_map::in, where_needed_map::out)
+ is det.
+
+dead_code__merge_where_needed_maps(CurrentPath,
+ WhereNeededMap1, WhereNeededMap2, WhereNeededMap) :-
+ map__to_assoc_list(WhereNeededMap1, WhereNeededList1),
+ dead_code__add_where_needed_list(WhereNeededList1, CurrentPath,
+ WhereNeededMap2, WhereNeededMap).
+
+:- pred dead_code__add_where_needed_list(assoc_list(prog_var, where_needed)::in,
+ goal_path::in, where_needed_map::in, where_needed_map::out) is det.
+
+dead_code__add_where_needed_list([], _, WhereNeededMap, WhereNeededMap).
+dead_code__add_where_needed_list([Var - BranchWhere | WhereNeededList],
+ CurrentPath, WhereNeededMap0, WhereNeededMap) :-
+ ( map__search(WhereNeededMap0, Var, OldWhere) ->
+ dead_code__where_needed_upper_bound(CurrentPath,
+ BranchWhere, OldWhere, CombinedWhere),
+ map__det_update(WhereNeededMap0, Var, CombinedWhere,
+ WhereNeededMap1)
+ ;
+ map__det_insert(WhereNeededMap0, Var, BranchWhere,
+ WhereNeededMap1)
+ ),
+ dead_code__add_where_needed_list(WhereNeededList, CurrentPath,
+ WhereNeededMap1, WhereNeededMap).
+
+% Given a where_needed_map, add to it the where_needed information for the
+% start of an alternative in a branched goal. This source is important,
+% because if the analysis *at the start of an alternative* says that the
+% variable is needed everywhere, the scope of this "everywhere" is only
+% that alternative.
+
+:- pred dead_code__add_alt_start(assoc_list(prog_var, where_needed)::in,
+ branch_point::in, int::in, goal_path::in,
+ where_needed_map::in, where_needed_map::out) is det.
+
+dead_code__add_alt_start([], _, _, _, WhereNeededMap, WhereNeededMap).
+dead_code__add_alt_start([Var - BranchWhere0 | WhereNeededList],
+ BranchPoint, BranchNum, CurrentPath,
+ WhereNeededMap0, WhereNeededMap) :-
+ (
+ BranchWhere0 = everywhere,
+ map__init(Empty),
+ set__singleton_set(BranchNumSet, BranchNum),
+ map__det_insert(Empty, BranchPoint, BranchNumSet, BranchMap),
+ BranchWhere = branches(BranchMap)
+ ;
+ BranchWhere0 = branches(_),
+ BranchWhere = BranchWhere0
+ ),
+ ( map__search(WhereNeededMap0, Var, OldWhere) ->
+ dead_code__where_needed_upper_bound(CurrentPath,
+ BranchWhere, OldWhere, CombinedWhere),
+ map__det_update(WhereNeededMap0, Var, CombinedWhere,
+ WhereNeededMap1)
+ ;
+ map__det_insert(WhereNeededMap0, Var, BranchWhere,
+ WhereNeededMap1)
+ ),
+ dead_code__add_alt_start(WhereNeededList, BranchPoint, BranchNum,
+ CurrentPath, WhereNeededMap1, WhereNeededMap).
+
+%---------------------------------------------------------------------------%
+
+:- pred dead_code__refine_goal(hlds_goal::in, refined_goal_map::in,
+ hlds_goal::out, refined_goal_map::out) is det.
+
+dead_code__refine_goal(Goal0, RefinedGoals0, Goal, RefinedGoals) :-
+ Goal0 = GoalExpr0 - GoalInfo0,
+ (
+ GoalExpr0 = unify(_, _, _, _, _),
+ Goal = Goal0,
+ RefinedGoals = RefinedGoals0
+ ;
+ GoalExpr0 = call(_, _, _, _, _, _),
+ Goal = Goal0,
+ RefinedGoals = RefinedGoals0
+ ;
+ GoalExpr0 = generic_call(_, _, _, _),
+ Goal = Goal0,
+ RefinedGoals = RefinedGoals0
+ ;
+ GoalExpr0 = pragma_c_code(_, _, _, _, _, _, _),
+ Goal = Goal0,
+ RefinedGoals = RefinedGoals0
+ ;
+ GoalExpr0 = par_conj(_, _),
+ Goal = Goal0,
+ RefinedGoals = RefinedGoals0
+ ;
+ GoalExpr0 = conj(Conjuncts0),
+ dead_code__refine_conj(Conjuncts0, RefinedGoals0,
+ Conjuncts, RefinedGoals),
+ GoalExpr = conj(Conjuncts),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = switch(SwitchVar, CanFail, Cases0, StoreMap),
+ goal_info_get_goal_path(GoalInfo0, GoalPath),
+ dead_code__refine_cases(Cases0, RefinedGoals0, GoalPath, 1,
+ Cases, RefinedGoals),
+ GoalExpr = switch(SwitchVar, CanFail, Cases, StoreMap),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = disj(Disjuncts0, StoreMap),
+ goal_info_get_goal_path(GoalInfo0, GoalPath),
+ dead_code__refine_disj(Disjuncts0, RefinedGoals0, GoalPath, 1,
+ Disjuncts, RefinedGoals),
+ GoalExpr = disj(Disjuncts, StoreMap),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = if_then_else(Quant, Cond0, Then0, Else0, StoreMap),
+ goal_info_get_goal_path(GoalInfo0, GoalPath),
+ dead_code__refine_ite(Cond0, Then0, Else0, RefinedGoals0,
+ GoalPath, Cond, Then, Else, RefinedGoals),
+ GoalExpr = if_then_else(Quant, Cond, Then, Else, StoreMap),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = not(NegGoal0),
+ dead_code__refine_goal(NegGoal0, RefinedGoals0,
+ NegGoal, RefinedGoals),
+ GoalExpr = not(NegGoal),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = some(Vars, CanFail, SomeGoal0),
+ dead_code__refine_goal(SomeGoal0, RefinedGoals0,
+ SomeGoal, RefinedGoals),
+ GoalExpr = some(Vars, CanFail, SomeGoal),
+ Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = bi_implication(_, _),
+ error("bi-implication in dead_code__refine_goal")
+ ).
+
+:- pred dead_code__refine_conj(list(hlds_goal)::in, refined_goal_map::in,
+ list(hlds_goal)::out, refined_goal_map::out) is det.
+
+dead_code__refine_conj([], RefinedGoals, [], RefinedGoals).
+dead_code__refine_conj([Goal0 | Goals0], RefinedGoals0, Goals, RefinedGoals) :-
+ dead_code__refine_goal(Goal0, RefinedGoals0, HeadGoal, RefinedGoals1),
+ dead_code__refine_conj(Goals0, RefinedGoals1, TailGoals, RefinedGoals),
+ ( HeadGoal = conj(HeadGoals) - _ ->
+ list__append(HeadGoals, TailGoals, Goals)
+ ;
+ Goals = [HeadGoal | TailGoals]
+ ).
+
+:- pred dead_code__refine_cases(list(case)::in, refined_goal_map::in,
+ goal_path::in, int::in, list(case)::out, refined_goal_map::out) is det.
+
+dead_code__refine_cases([], RefinedGoals, _, _, [], RefinedGoals).
+dead_code__refine_cases([case(Var, Goal0) | Cases0], RefinedGoals0,
+ GoalPath, BranchNum,
+ [case(Var, Goal) | Cases], RefinedGoals) :-
+ dead_code__refine_goal(Goal0, RefinedGoals0, Goal1, RefinedGoals1),
+ ( map__search(RefinedGoals1, GoalPath - BranchNum, ToInsertGoals) ->
+ dead_code__insert_refine_goals(ToInsertGoals, Goal1, Goal),
+ map__delete(RefinedGoals1, GoalPath - BranchNum, RefinedGoals2)
+ ;
+ Goal = Goal1,
+ RefinedGoals2 = RefinedGoals1
+ ),
+ dead_code__refine_cases(Cases0, RefinedGoals2,
+ GoalPath, BranchNum + 1, Cases, RefinedGoals).
+
+:- pred dead_code__refine_disj(list(hlds_goal)::in, refined_goal_map::in,
+ goal_path::in, int::in, list(hlds_goal)::out, refined_goal_map::out)
+ is det.
+
+dead_code__refine_disj([], RefinedGoals, _, _, [], RefinedGoals).
+dead_code__refine_disj([Goal0 | Goals0], RefinedGoals0,
+ GoalPath, BranchNum, [Goal | Goals], RefinedGoals) :-
+ dead_code__refine_goal(Goal0, RefinedGoals0, Goal1, RefinedGoals1),
+ ( map__search(RefinedGoals1, GoalPath - BranchNum, ToInsertGoals) ->
+ dead_code__insert_refine_goals(ToInsertGoals, Goal1, Goal),
+ map__delete(RefinedGoals1, GoalPath - BranchNum, RefinedGoals2)
+ ;
+ Goal = Goal1,
+ RefinedGoals2 = RefinedGoals1
+ ),
+ dead_code__refine_disj(Goals0, RefinedGoals2,
+ GoalPath, BranchNum + 1, Goals, RefinedGoals).
+
+:- pred dead_code__refine_ite(hlds_goal::in, hlds_goal::in, hlds_goal::in,
+ refined_goal_map::in, goal_path::in,
+ hlds_goal::out, hlds_goal::out, hlds_goal::out, refined_goal_map::out)
+ is det.
+
+dead_code__refine_ite(Cond0, Then0, Else0, RefinedGoals0, GoalPath,
+ Cond, Then, Else, RefinedGoals) :-
+ dead_code__refine_goal(Cond0, RefinedGoals0, Cond, RefinedGoals1),
+ dead_code__refine_goal(Then0, RefinedGoals1, Then1, RefinedGoals2),
+ dead_code__refine_goal(Else0, RefinedGoals2, Else1, RefinedGoals3),
+
+ ( map__search(RefinedGoals3, GoalPath - 1, ToInsertGoalsThen) ->
+ dead_code__insert_refine_goals(ToInsertGoalsThen, Then1, Then),
+ map__delete(RefinedGoals3, GoalPath - 1, RefinedGoals4)
+ ;
+ Then = Then1,
+ RefinedGoals4 = RefinedGoals3
+ ),
+ ( map__search(RefinedGoals4, GoalPath - 2, ToInsertGoalsElse) ->
+ dead_code__insert_refine_goals(ToInsertGoalsElse, Else1, Else),
+ map__delete(RefinedGoals4, GoalPath - 2, RefinedGoals)
+ ;
+ Else = Else1,
+ RefinedGoals = RefinedGoals4
+ ).
+
+:- pred dead_code__insert_refine_goals(list(hlds_goal)::in, hlds_goal::in,
+ hlds_goal::out) is det.
+
+dead_code__insert_refine_goals(ToInsertGoals, Goal0, Goal) :-
+ list__append(ToInsertGoals, [Goal0], Conj),
+ % XXX GoalInfo0
+ Goal0 = _ - GoalInfo0,
+ conj_list_to_goal(Conj, GoalInfo0, Goal).
+
+%-----------------------------------------------------------------------------%
+
+% Given two sets of requirements about where a goal is needed, return a single
+% requirement that contains all the demands. The main purpose of this predicate
+% is to discover when the union of two sets of requirements (e.g. branch sets
+% {b1,b2} and {b3} covers all computation paths.
+
+:- pred dead_code__where_needed_upper_bound(goal_path::in, where_needed::in,
+ where_needed::in, where_needed::out) is det.
+
+dead_code__where_needed_upper_bound(CurrentPath, WhereNeededA, WhereNeededB,
+ WhereNeeded) :-
+ (
+ WhereNeededA = everywhere,
+ WhereNeeded = everywhere
+ ;
+ WhereNeededA = branches(BranchesA),
+ (
+ WhereNeededB = everywhere,
+ WhereNeeded = everywhere
+ ;
+ WhereNeededB = branches(BranchesB),
+ dead_code__where_needed_branches_upper_bound(
+ CurrentPath, BranchesA, BranchesB, WhereNeeded)
+ )
+ ).
+
+:- pred dead_code__where_needed_branches_upper_bound(goal_path::in,
+ where_needed_branches::in, where_needed_branches::in,
+ where_needed::out) is det.
+
+dead_code__where_needed_branches_upper_bound(CurrentPath, BranchesA, BranchesB,
+ WhereNeeded) :-
+ % should select smaller map to convert to list
+ map__to_assoc_list(BranchesA, BranchesList),
+ dead_code__where_needed_branches_upper_bound_2(CurrentPath,
+ BranchesList, BranchesB, WhereNeeded).
+
+:- pred dead_code__where_needed_branches_upper_bound_2(goal_path::in,
+ assoc_list(branch_point, set(int))::in, where_needed_branches::in,
+ where_needed::out) is det.
+
+dead_code__where_needed_branches_upper_bound_2(_, [],
+ Branches, branches(Branches)).
+dead_code__where_needed_branches_upper_bound_2(CurrentPath, [First | Rest],
+ Branches0, WhereNeeded) :-
+ First = BranchPoint - NewAlts,
+ ( map__search(Branches0, BranchPoint, OldAlts) ->
+ set__union(OldAlts, NewAlts, Alts),
+ BranchPoint = branch_point(GoalPath, BranchAlts),
+ ( dead_code__branch_point_is_complete(BranchAlts, Alts) ->
+ (
+ dead_code__get_parent_branch_point(GoalPath,
+ ParentGoalPath, ParentGoalPathStep,
+ ParentBranchAlt, ParentBranchNum),
+ \+ list__remove_suffix(CurrentPath,
+ [ParentGoalPathStep | ParentGoalPath],
+ _)
+ ->
+ map__delete(Branches0, BranchPoint, Branches1),
+ ParentBranchPoint = branch_point(
+ ParentGoalPath, ParentBranchAlt),
+ set__singleton_set(ParentAlts,
+ ParentBranchNum),
+ dead_code__where_needed_branches_upper_bound_2(
+ CurrentPath,
+ [ParentBranchPoint - ParentAlts
+ | Rest],
+ Branches1, WhereNeeded)
+ ;
+ WhereNeeded = everywhere
+ )
+ ;
+ map__det_update(Branches0, BranchPoint, Alts,
+ Branches1),
+ dead_code__where_needed_branches_upper_bound_2(
+ CurrentPath, Rest, Branches1, WhereNeeded)
+ )
+ ;
+ map__det_insert(Branches0, BranchPoint, NewAlts, Branches1),
+ dead_code__where_needed_branches_upper_bound_2(CurrentPath,
+ Rest, Branches1, WhereNeeded)
+ ).
+
+:- pred dead_code__get_parent_branch_point(goal_path::in, goal_path::out,
+ goal_path_step::out, branch_alts::out, int::out) is semidet.
+
+dead_code__get_parent_branch_point([First | Rest], Parent, ParentStep,
+ BranchAlt, BranchNum) :-
+ ( First = switch(Arm, NumAlts) ->
+ Parent = Rest,
+ ParentStep = First,
+ BranchAlt = switch(NumAlts),
+ BranchNum = Arm
+ ; First = ite_then ->
+ Parent = Rest,
+ ParentStep = First,
+ BranchAlt = ite,
+ BranchNum = 1
+ ; First = ite_else ->
+ Parent = Rest,
+ ParentStep = First,
+ BranchAlt = ite,
+ BranchNum = 2
+ ;
+ dead_code__get_parent_branch_point(Rest, Parent, ParentStep,
+ BranchAlt, BranchNum)
+ ).
+
+:- pred dead_code__branch_point_is_complete(branch_alts::in, set(int)::in)
+ is semidet.
+
+dead_code__branch_point_is_complete(ite, Alts) :-
+ set__count(Alts, NumAlts),
+ NumAlts = 2.
+dead_code__branch_point_is_complete(switch(NumFunctors), Alts) :-
+ set__count(Alts, NumAlts),
+ NumAlts = NumFunctors.
+
+%---------------------------------------------------------------------------%
Index: compiler/goal_path.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/goal_path.m,v
retrieving revision 1.7
diff -u -b -r1.7 goal_path.m
--- compiler/goal_path.m 1999/10/25 03:48:49 1.7
+++ compiler/goal_path.m 2000/07/17 06:42:06
@@ -20,74 +20,105 @@
:- implementation.
-:- import_module hlds_goal.
-:- import_module int, list, std_util, require.
+:- import_module prog_data, hlds_data, hlds_goal, type_util.
+:- import_module char, int, list, map, std_util, require.
-goal_path__fill_slots(Proc0, _ModuleInfo, Proc) :-
+:- type slot_info
+ ---> slot_info(
+ vartypes,
+ module_info
+ ).
+
+goal_path__fill_slots(Proc0, ModuleInfo, Proc) :-
% The ModuleInfo argument is there just for passes_aux
proc_info_goal(Proc0, Goal0),
- fill_goal_slots(Goal0, [], Goal),
+ proc_info_vartypes(Proc0, VarTypes),
+ SlotInfo = slot_info(VarTypes, ModuleInfo),
+ fill_goal_slots(Goal0, [], SlotInfo, Goal),
proc_info_set_goal(Proc0, Goal, Proc).
-:- pred fill_goal_slots(hlds_goal::in, goal_path::in, hlds_goal::out) is det.
+:- pred fill_goal_slots(hlds_goal::in, goal_path::in, slot_info::in,
+ hlds_goal::out) is det.
-fill_goal_slots(Expr0 - Info0, Path0, Expr - Info) :-
+fill_goal_slots(Expr0 - Info0, Path0, SlotInfo, Expr - Info) :-
goal_info_set_goal_path(Info0, Path0, Info),
- fill_expr_slots(Expr0, Path0, Expr).
+ fill_expr_slots(Expr0, Path0, SlotInfo, Expr).
-:- pred fill_expr_slots(hlds_goal_expr::in, goal_path::in,
+:- pred fill_expr_slots(hlds_goal_expr::in, goal_path::in, slot_info::in,
hlds_goal_expr::out) is det.
-fill_expr_slots(conj(Goals0), Path0, conj(Goals)) :-
- fill_conj_slots(Goals0, Path0, 0, Goals).
-fill_expr_slots(par_conj(Goals0, SM), Path0, par_conj(Goals, SM)) :-
- fill_conj_slots(Goals0, Path0, 0, Goals).
-fill_expr_slots(disj(Goals0, B), Path0, disj(Goals, B)) :-
- fill_disj_slots(Goals0, Path0, 0, Goals).
-fill_expr_slots(switch(A, B, Cases0, D), Path0, switch(A, B, Cases, D)) :-
- fill_switch_slots(Cases0, Path0, 0, Cases).
-fill_expr_slots(not(Goal0), Path0, not(Goal)) :-
- fill_goal_slots(Goal0, [neg | Path0], Goal).
-fill_expr_slots(some(A, B, Goal0), Path0, some(A, B, Goal)) :-
- fill_goal_slots(Goal0, [exist | Path0], Goal).
-fill_expr_slots(if_then_else(A, Cond0, Then0, Else0, E), Path0,
+fill_expr_slots(conj(Goals0), Path0, SlotInfo, conj(Goals)) :-
+ fill_conj_slots(Goals0, Path0, 0, SlotInfo, Goals).
+fill_expr_slots(par_conj(Goals0, SM), Path0, SlotInfo, par_conj(Goals, SM)) :-
+ fill_conj_slots(Goals0, Path0, 0, SlotInfo, Goals).
+fill_expr_slots(disj(Goals0, B), Path0, SlotInfo, disj(Goals, B)) :-
+ fill_disj_slots(Goals0, Path0, 0, SlotInfo, Goals).
+fill_expr_slots(switch(Var, B, Cases0, D), Path0, SlotInfo,
+ switch(Var, B, Cases, D)) :-
+ SlotInfo = slot_info(VarTypes, ModuleInfo),
+ module_info_types(ModuleInfo, TypeTable),
+ map__lookup(VarTypes, Var, Type),
+ (
+ type_to_type_id(Type, TypeId, _),
+ ( map__search(TypeTable, TypeId, TypeDefn) ->
+ hlds_data__get_type_defn_body(TypeDefn, Body),
+ Body = du_type(_, ConsTable, _, _),
+ map__count(ConsTable, Count)
+ ; TypeId = unqualified("character") - 0 ->
+ char__max_char_value(MaxCharValue),
+ char__min_char_value(MinCharValue),
+ Count = MaxCharValue - MinCharValue + 1
+ ;
+ Count = -1
+ )
+ ->
+ NumCases = Count
+ ;
+ error("fill_expr_slots: cannot count switch alternatives")
+ ),
+ fill_switch_slots(Cases0, Path0, 0, NumCases, SlotInfo, Cases).
+fill_expr_slots(not(Goal0), Path0, SlotInfo, not(Goal)) :-
+ fill_goal_slots(Goal0, [neg | Path0], SlotInfo, Goal).
+fill_expr_slots(some(A, B, Goal0), Path0, SlotInfo, some(A, B, Goal)) :-
+ fill_goal_slots(Goal0, [exist | Path0], SlotInfo, Goal).
+fill_expr_slots(if_then_else(A, Cond0, Then0, Else0, E), Path0, SlotInfo,
if_then_else(A, Cond, Then, Else, E)) :-
- fill_goal_slots(Cond0, [ite_cond | Path0], Cond),
- fill_goal_slots(Then0, [ite_then | Path0], Then),
- fill_goal_slots(Else0, [ite_else | Path0], Else).
-fill_expr_slots(call(A,B,C,D,E,F), _Path0, call(A,B,C,D,E,F)).
-fill_expr_slots(generic_call(A,B,C,D), _Path0, generic_call(A,B,C,D)).
-fill_expr_slots(unify(A,B,C,D,E), _Path0, unify(A,B,C,D,E)).
-fill_expr_slots(pragma_c_code(A,B,C,D,E,F,G), _Path0,
+ fill_goal_slots(Cond0, [ite_cond | Path0], SlotInfo, Cond),
+ fill_goal_slots(Then0, [ite_then | Path0], SlotInfo, Then),
+ fill_goal_slots(Else0, [ite_else | Path0], SlotInfo, Else).
+fill_expr_slots(call(A,B,C,D,E,F), _Path0, _Slot, call(A,B,C,D,E,F)).
+fill_expr_slots(generic_call(A,B,C,D), _Path0, _Slot, generic_call(A,B,C,D)).
+fill_expr_slots(unify(A,B,C,D,E), _Path0, _Slot, unify(A,B,C,D,E)).
+fill_expr_slots(pragma_c_code(A,B,C,D,E,F,G), _Path0, _Slot,
pragma_c_code(A,B,C,D,E,F,G)).
-fill_expr_slots(bi_implication(_, _), _, _) :-
+fill_expr_slots(bi_implication(_, _), _, _, _) :-
% these should have been expanded out by now
error("fill_expr_slots: unexpected bi_implication").
:- pred fill_conj_slots(list(hlds_goal)::in, goal_path::in, int::in,
- list(hlds_goal)::out) is det.
+ slot_info::in, list(hlds_goal)::out) is det.
-fill_conj_slots([], _, _, []).
-fill_conj_slots([Goal0 | Goals0], Path0, N0, [Goal | Goals]) :-
+fill_conj_slots([], _, _, _, []).
+fill_conj_slots([Goal0 | Goals0], Path0, N0, SlotInfo, [Goal | Goals]) :-
N1 is N0 + 1,
- fill_goal_slots(Goal0, [conj(N1) | Path0], Goal),
- fill_conj_slots(Goals0, Path0, N1, Goals).
+ fill_goal_slots(Goal0, [conj(N1) | Path0], SlotInfo, Goal),
+ fill_conj_slots(Goals0, Path0, N1, SlotInfo, Goals).
:- pred fill_disj_slots(list(hlds_goal)::in, goal_path::in, int::in,
- list(hlds_goal)::out) is det.
+ slot_info::in, list(hlds_goal)::out) is det.
-fill_disj_slots([], _, _, []).
-fill_disj_slots([Goal0 | Goals0], Path0, N0, [Goal | Goals]) :-
+fill_disj_slots([], _, _, _, []).
+fill_disj_slots([Goal0 | Goals0], Path0, N0, SlotInfo, [Goal | Goals]) :-
N1 is N0 + 1,
- fill_goal_slots(Goal0, [disj(N1) | Path0], Goal),
- fill_disj_slots(Goals0, Path0, N1, Goals).
+ fill_goal_slots(Goal0, [disj(N1) | Path0], SlotInfo, Goal),
+ fill_disj_slots(Goals0, Path0, N1, SlotInfo, Goals).
-:- pred fill_switch_slots(list(case)::in, goal_path::in, int::in,
- list(case)::out) is det.
+:- pred fill_switch_slots(list(case)::in, goal_path::in, int::in, int::in,
+ slot_info::in, list(case)::out) is det.
-fill_switch_slots([], _, _, []).
-fill_switch_slots([case(A, Goal0) | Cases0], Path0, N0,
+fill_switch_slots([], _, _, _, _, []).
+fill_switch_slots([case(A, Goal0) | Cases0], Path0, N0, NumCases, SlotInfo,
[case(A, Goal) | Cases]) :-
N1 is N0 + 1,
- fill_goal_slots(Goal0, [switch(N1) | Path0], Goal),
- fill_switch_slots(Cases0, Path0, N1, Cases).
+ fill_goal_slots(Goal0, [switch(N1, NumCases) | Path0], SlotInfo, Goal),
+ fill_switch_slots(Cases0, Path0, N1, NumCases, SlotInfo, Cases).
Index: compiler/hlds_goal.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_goal.m,v
retrieving revision 1.71
diff -u -b -r1.71 hlds_goal.m
--- compiler/hlds_goal.m 2000/05/22 17:59:25 1.71
+++ compiler/hlds_goal.m 2000/07/18 05:54:05
@@ -647,14 +647,20 @@
% We can think of the goal that defines a procedure to be a tree,
% whose leaves are primitive goals and whose interior nodes are
% compound goals. These two types describe the position of a goal
- % in this tree. The first says which branch to take at an interior
- % node (the integer counts start at one). The second gives the
- % sequence of steps from the root to the given goal *in reverse order*,
- % so that the step closest to the root is last.
+ % in this tree. A goal_path_step type says which branch to take at an
+ % interior node; the integer counts start at one. (For switches,
+ % the second int gives the total number of function symbols in the type
+ % of the switched-on var; for builtin types such as integer and string,
+ % for which this number is effectively infinite, we store a negative
+ % number.) The goal_path type gives the sequence of steps from the root
+ % to the given goal *in reverse order*, so that the step closest to
+ % the root is last. (Keeping the list in reverse order makes the
+ % common operations constant-time instead of linear in the length
+ % of the list.)
:- type goal_path_step ---> conj(int)
; disj(int)
- ; switch(int)
+ ; switch(int, int)
; ite_cond
; ite_then
; ite_else
Index: compiler/hlds_out.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_out.m,v
retrieving revision 1.237
diff -u -b -r1.237 hlds_out.m
--- compiler/hlds_out.m 2000/04/14 08:37:51 1.237
+++ compiler/hlds_out.m 2000/07/17 06:42:07
@@ -240,7 +240,7 @@
:- import_module mercury_to_mercury, globals, options, purity, special_pred.
:- import_module llds_out, prog_out, prog_util, (inst), instmap, trace.
-:- import_module rl, termination, term_errors, check_typeclass.
+:- import_module rl, code_util, termination, term_errors, check_typeclass.
:- import_module int, string, set, assoc_list, map, multi_map.
:- import_module require, getopt, std_util, term_io, varset.
@@ -675,15 +675,12 @@
->
[]
;
- % We dump unification predicates if suboption
- % 'U' is on. We don't really need that
- % information to understand how the program has
- % been transformed.
+ % We dump unification and other compiler-generated
+ % special predicates if suboption 'U' is on. We don't
+ % need that information to understand how the program
+ % has been transformed.
{ \+ string__contains_char(Verbose, 'U') },
- { pred_info_arity(PredInfo, Arity) },
- { Arity = 2 },
- { pred_info_name(PredInfo, PredName) },
- { PredName = "__Unify__" }
+ { code_util__compiler_generated(PredInfo) }
->
[]
;
Index: compiler/hlds_pred.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_pred.m,v
retrieving revision 1.76
diff -u -b -r1.76 hlds_pred.m
--- compiler/hlds_pred.m 2000/06/01 08:32:34 1.76
+++ compiler/hlds_pred.m 2000/07/18 05:54:06
@@ -20,7 +20,7 @@
:- implementation.
:- import_module code_aux, goal_util, make_hlds, prog_util.
-:- import_module mode_util, type_util, options.
+:- import_module inst_match, mode_util, type_util, options.
:- import_module int, string, require, assoc_list.
%-----------------------------------------------------------------------------%
@@ -1408,6 +1408,18 @@
list(type), list(prog_var), proc_info).
:- mode proc_info_create_vars_from_types(in, in, out, out) is det.
+ % Given a procedure, return a list of all its headvars whose inst
+ % is changed by the procedure.
+:- pred proc_info_changed_inst_head_vars(module_info, proc_info,
+ list(prog_var)).
+:- mode proc_info_changed_inst_head_vars(in, in, out) is det.
+
+ % Given a procedure, return a list of all its headvars whose inst
+ % is not changed by the procedure.
+:- pred proc_info_unchanged_inst_head_vars(module_info, proc_info,
+ list(prog_var)).
+:- mode proc_info_unchanged_inst_head_vars(in, in, out) is det.
+
% Return true if the interface of the given procedure must include
% typeinfos for all the type variables in the types of the arguments.
:- pred proc_interface_should_use_typeinfo_liveness(pred_info, proc_id,
@@ -1742,6 +1754,29 @@
NewVars, Types, VarTypes),
proc_info_set_varset(ProcInfo0, VarSet, ProcInfo1),
proc_info_set_vartypes(ProcInfo1, VarTypes, ProcInfo).
+
+proc_info_changed_inst_head_vars(ModuleInfo, ProcInfo, ChangedInstHeadVars) :-
+ proc_info_headvars(ProcInfo, HeadVars),
+ proc_info_argmodes(ProcInfo, ArgModes),
+ assoc_list__from_corresponding_lists(HeadVars, ArgModes, HeadVarModes),
+ IsInstChanged = lambda([VarMode::in, Var::out] is semidet, (
+ VarMode = Var - Mode,
+ mode_get_insts(ModuleInfo, Mode, Inst1, Inst2),
+ \+ inst_matches_binding(Inst1, Inst2, ModuleInfo)
+ )),
+ list__filter_map(IsInstChanged, HeadVarModes, ChangedInstHeadVars).
+
+proc_info_unchanged_inst_head_vars(ModuleInfo, ProcInfo,
+ UnchangedInstHeadVars) :-
+ proc_info_headvars(ProcInfo, HeadVars),
+ proc_info_argmodes(ProcInfo, ArgModes),
+ assoc_list__from_corresponding_lists(HeadVars, ArgModes, HeadVarModes),
+ IsInstUnchanged = lambda([VarMode::in, Var::out] is semidet, (
+ VarMode = Var - Mode,
+ mode_get_insts(ModuleInfo, Mode, Inst1, Inst2),
+ inst_matches_binding(Inst1, Inst2, ModuleInfo)
+ )),
+ list__filter_map(IsInstUnchanged, HeadVarModes, UnchangedInstHeadVars).
proc_interface_should_use_typeinfo_liveness(PredInfo, ProcId, Globals,
InterfaceTypeInfoLiveness) :-
Index: compiler/mercury_compile.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mercury_compile.m,v
retrieving revision 1.167
diff -u -b -r1.167 mercury_compile.m
--- compiler/mercury_compile.m 2000/06/16 16:37:11 1.167
+++ compiler/mercury_compile.m 2000/07/18 06:15:46
@@ -43,7 +43,7 @@
:- import_module check_typeclass, intermod, trans_opt, table_gen, (lambda).
:- import_module type_ctor_info, termination, higher_order, accumulator.
:- import_module inlining, deforest, dnf, magic, dead_proc_elim.
-:- import_module unused_args, lco.
+:- import_module unused_args, dead_code, lco.
% the LLDS back-end
:- import_module saved_vars, liveness.
@@ -1043,9 +1043,12 @@
mercury_compile__maybe_unused_args(HLDS36, Verbose, Stats, HLDS39),
mercury_compile__maybe_dump_hlds(HLDS39, "39", "unused_args"),
- mercury_compile__maybe_lco(HLDS39, Verbose, Stats, HLDS40),
- mercury_compile__maybe_dump_hlds(HLDS40, "40", "lco"),
+ mercury_compile__maybe_dead_code(HLDS39, Verbose, Stats, HLDS40),
+ mercury_compile__maybe_dump_hlds(HLDS40, "40", "dead_code"),
+ mercury_compile__maybe_lco(HLDS40, Verbose, Stats, HLDS42), !,
+ mercury_compile__maybe_dump_hlds(HLDS42, "42", "lco"), !,
+
% DNF transformations should be after inlining.
mercury_compile__maybe_transform_dnf(HLDS40, Verbose, Stats, HLDS44),
mercury_compile__maybe_dump_hlds(HLDS44, "44", "dnf"),
@@ -1853,6 +1856,24 @@
maybe_write_string(Verbose, "% Finding unused arguments ...\n"),
maybe_flush_output(Verbose),
unused_args__process_module(HLDS0, HLDS),
+ maybe_write_string(Verbose, "% done.\n"),
+ maybe_report_stats(Stats)
+ ;
+ { HLDS0 = HLDS }
+ ).
+
+:- pred mercury_compile__maybe_dead_code(module_info, bool, bool, module_info,
+ io__state, io__state).
+:- mode mercury_compile__maybe_dead_code(in, in, in, out, di, uo) is det.
+
+mercury_compile__maybe_dead_code(HLDS0, Verbose, Stats, HLDS) -->
+ globals__io_lookup_bool_option(dead_code, DeadCode),
+ ( { DeadCode = yes } ->
+ maybe_write_string(Verbose, "% Removing dead code from procedure bodies...\n"),
+ maybe_flush_output(Verbose),
+ process_all_nonimported_procs(
+ update_module_io(dead_code__process_proc_msg),
+ HLDS0, HLDS),
maybe_write_string(Verbose, "% done.\n"),
maybe_report_stats(Stats)
;
Index: compiler/options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.283
diff -u -b -r1.283 options.m
--- compiler/options.m 2000/06/28 07:42:04 1.283
+++ compiler/options.m 2000/07/18 05:54:17
@@ -294,6 +294,7 @@
; optimize_unused_args
; intermod_unused_args
; optimize_higher_order
+ ; dead_code
; type_specialization
; user_guided_type_specialization
; higher_order_size_limit
@@ -659,6 +660,7 @@
optimize_unused_args - bool(no),
intermod_unused_args - bool(no),
optimize_higher_order - bool(no),
+ dead_code - bool(no),
type_specialization - bool(no),
user_guided_type_specialization - bool(no),
higher_order_size_limit - int(20),
@@ -1007,6 +1009,7 @@
long_option("intermod-unused-args", intermod_unused_args).
long_option("optimize-higher-order", optimize_higher_order).
long_option("optimise-higher-order", optimize_higher_order).
+long_option("dead-code", dead_code).
long_option("type-specialization", type_specialization).
long_option("type-specialisation", type_specialization).
long_option("user-guided-type-specialization",
Index: compiler/trace.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/trace.m,v
retrieving revision 1.32
diff -u -b -r1.32 trace.m
--- compiler/trace.m 2000/04/26 05:40:35 1.32
+++ compiler/trace.m 2000/07/17 06:42:19
@@ -468,7 +468,7 @@
{
Path = [LastStep | _],
(
- LastStep = switch(_),
+ LastStep = switch(_, _),
PortPrime = switch
;
LastStep = disj(_),
@@ -786,7 +786,7 @@
trace__path_step_to_string(disj(N), Str) :-
string__int_to_string(N, NStr),
string__append_list(["d", NStr, ";"], Str).
-trace__path_step_to_string(switch(N), Str) :-
+trace__path_step_to_string(switch(N, _), Str) :-
string__int_to_string(N, NStr),
string__append_list(["s", NStr, ";"], Str).
trace__path_step_to_string(ite_cond, "?;").
Index: compiler/unused_args.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/unused_args.m,v
retrieving revision 1.62
diff -u -b -r1.62 unused_args.m
--- compiler/unused_args.m 1999/11/11 23:12:15 1.62
+++ compiler/unused_args.m 2000/07/17 06:42:20
@@ -247,13 +247,10 @@
OptProcs1 = OptProcs0,
VarUsage1 = VarUsage0
;
- proc_info_argmodes(ProcInfo, ArgModes),
- proc_info_headvars(ProcInfo, HeadVars),
proc_info_vartypes(ProcInfo, VarTypes),
map__keys(VarTypes, Vars),
initialise_vardep(VarDep0, Vars, VarDep1),
- setup_output_args(ModuleInfo, HeadVars,
- ArgModes, VarDep1, VarDep2),
+ setup_output_args(ModuleInfo, ProcInfo, VarDep1, VarDep2),
module_info_globals(ModuleInfo, Globals),
proc_interface_should_use_typeinfo_liveness(PredInfo, ProcId,
@@ -327,32 +324,13 @@
% Get output arguments for a procedure given the headvars and the
% argument modes, and set them as used.
-:- pred setup_output_args(module_info::in, list(prog_var)::in, list(mode)::in,
+:- pred setup_output_args(module_info::in, proc_info::in,
var_dep::in, var_dep::out) is det.
-setup_output_args(ModuleInfo, HVars, ArgModes, VarDep0, VarDep) :-
- (
- HVars = [Var | Vars], ArgModes = [Mode | Modes]
- ->
- (
- % Any argument which has its instantiatedness
- % changed by the predicate is used.
- mode_get_insts(ModuleInfo, Mode, Inst1, Inst2),
- \+ inst_matches_binding(Inst1, Inst2, ModuleInfo)
- ->
- set_var_used(VarDep0, Var, VarDep1)
- ;
- VarDep1 = VarDep0
- ),
- setup_output_args(ModuleInfo, Vars, Modes, VarDep1, VarDep)
- ;
- HVars = [], ArgModes = []
- ->
- VarDep = VarDep0
- ;
- error("setup_output_args: invalid call")
- ).
-
+setup_output_args(ModuleInfo, ProcInfo, VarDep0, VarDep) :-
+ proc_info_changed_inst_head_vars(ModuleInfo, ProcInfo,
+ ChangedInstHeadVars),
+ list__foldl(set_var_used, ChangedInstHeadVars, VarDep0, VarDep).
% searches for the dependencies of a variable, succeeds if the variable
% is definitely used
@@ -391,9 +369,9 @@
set_list_vars_used(UseInfo0, Vars, UseInfo) :-
map__delete_list(UseInfo0, Vars, UseInfo).
-:- pred set_var_used(var_dep::in, prog_var::in, var_dep::out) is det.
+:- pred set_var_used(prog_var::in, var_dep::in, var_dep::out) is det.
-set_var_used(UseInfo0, Var, UseInfo) :-
+set_var_used(Var, UseInfo0, UseInfo) :-
map__delete(UseInfo0, Var, UseInfo).
@@ -424,7 +402,7 @@
% handle switch
traverse_goal(ModuleInfo, switch(Var, _, Cases, _), UseInf0, UseInf) :-
- set_var_used(UseInf0, Var, UseInf1),
+ set_var_used(Var, UseInf0, UseInf1),
list_case_to_list_goal(Cases, Goals),
traverse_list_of_goals(ModuleInfo, Goals, UseInf1, UseInf).
@@ -471,13 +449,13 @@
% cases to handle all the different types of unification
traverse_goal(_, unify(_, _, _, simple_test(Var1, Var2),_), UseInf0, UseInf)
:-
- set_var_used(UseInf0, Var1, UseInf1),
- set_var_used(UseInf1, Var2, UseInf).
+ set_var_used(Var1, UseInf0, UseInf1),
+ set_var_used(Var2, UseInf1, UseInf).
traverse_goal(_, unify(_, _, _, assign(Var1, Var2), _), UseInf0, UseInf) :-
( local_var_is_used(UseInf0, Var1) ->
% if Var1 used to instantiate an output argument, Var2 used
- set_var_used(UseInf0, Var2, UseInf)
+ set_var_used(Var2, UseInf0, UseInf)
;
add_aliases(UseInf0, Var2, [Var1], UseInf)
).
@@ -497,7 +475,7 @@
CanFail = can_fail
->
% a deconstruction that can_fail uses its left arg
- set_var_used(UseInf2, Var1, UseInf)
+ set_var_used(Var1, UseInf2, UseInf)
;
UseInf = UseInf2
).
@@ -517,8 +495,8 @@
% with --error-check-only and polymorphism has not been run.
% Complicated unifications should only be var-var.
( Rhs = var(RhsVar) ->
- set_var_used(UseInf0, RhsVar, UseInf1),
- set_var_used(UseInf1, Var, UseInf)
+ set_var_used(RhsVar, UseInf0, UseInf1),
+ set_var_used(Var, UseInf1, UseInf)
;
error("complicated unifications should only be var-var")
).
@@ -714,7 +692,7 @@
)
->
% set the current variable to used
- set_var_used(LocalVars0, Var, LocalVars1),
+ set_var_used(Var, LocalVars0, LocalVars1),
Changed1 = yes
;
Changed1 = Changed0,
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/aditi
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/concurrency
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing library
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing tests
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/hard_coded
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing trial
cvs diff: Diffing util
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to: mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions: mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------
More information about the developers
mailing list