daikon
Class PptCombined
Object
Ppt
PptTopLevel
PptCombined
- All Implemented Interfaces:
- Serializable
public class PptCombined
- extends PptTopLevel
A program point which consists of a number of program points. Invariants
are looked for over all combinations of variables from all of the program
points that make up the combined ppt.
- See Also:
- Serialized Form
|
Nested Class Summary |
static class |
PptCombined.PpSizeComparator
Given a map, sort elements of the map according to the size of the mapped-to list. |
|
Field Summary |
static String |
dkconfig_asm_path_name
If non-null, we will compute redundant binary variables
when creating a CombinedProgramPoint, using
the assembly information in the file specified. |
static String |
dkconfig_rvars_file
If redundant variables are being computed, the results
of the redundancy analysis are printed to this stream. |
List<PptTopLevel> |
ppts
List of ppts that make up this combined ppt |
Map<String,String> |
rvars
Map from the name of a redundant variable to its leader (the earliest
executed variable with guaranteed statically to have the same value). |
| Fields inherited from class PptTopLevel |
bb_length, children, combined_ppt, combined_ppts_init, combined_subsumed, combined_subsumed_by, constants, debug_varinfo, debugAddImplications, debugConditional, debugEqualTo, debugFlow, debugInstantiate, debugMerge, debugNISStats, debugTimeMerge, dkconfig_pairwise_implications, dkconfig_remove_merged_invs, equality_view, first_pass_with_sample, flags, function_id, icfp, in_merge, instantiated_inv_cnt, instantiated_slice_cnt, invariants_merged, invariants_removed, joiner_view, last_values, name, num_declvars, num_orig_vars, num_static_constant_vars, num_tracevars, parent_relations, parents, ppt_name, ppt_successors, predecessors, redundant_invs, redundant_invs_equality, splitters, type |
| Methods inherited from class PptTopLevel |
add_bottom_up, addConditions, addImplications, addSlice, addViews, all_predecessors_goto, all_predecessors_goto, all_successors_goto, all_successors_goto, bb_offset, build_permute, check_implied_canonical, check_implied_canonical, check_implied_canonical, check_implied, check_implied, check_implied, clean_for_merge, cond_iterator, connected, connected, const_inv_cnt, const_slice_cnt, create_derived_variables, create_equality_inv, debug_invs, debug_print_slice_info, debug_print_tree, debug_unary_info, debugSlices, equality_sets_txt, find_assignment_inv, find_combined_ppt_leader, find_inv_by_class, findSlice_unordered, findSlice_unordered, findSlice_unordered, findSlice, findSlice, findSlice, findSlice, get_missingOutOfBounds, get_or_instantiate_slice, get_or_instantiate_slice, get_or_instantiate_slice, get_or_instantiate_slice, get_temp_slice, get_temp_slice, getInvariants, getParamVars, has_parent, has_splitters, incSampleNumber, instantiate_views_and_invariants, inv_add, invariant_cnt_by_class, invariant_cnt, invariants_iterator, invariants_vector, is_basic_block, is_class, is_combined_exit, is_constant, is_empty, is_enter, is_equal, is_exit, is_less_equal, is_missing, is_nonzero, is_object, is_prev_constant, is_prev_missing, is_slice_ok, is_slice_ok, is_slice_ok, is_slice_ok, is_subexit, is_subsequence, is_subset, mark_implied_via_simplify, merge_conditionals, merge_invs_multiple_children, merge_invs_one_child, mergeInvs, name, num_array_vars, num_samples, num_samples, num_samples, num_samples, num_values, num_values, num_values, numViews, parent_vis, postProcessEquality, print_equality_stats, processOmissions, remove_child_invs, remove_equality_invariants, remove_implications, remove_invs, removeSlice, repCheck, simplify_variable_names, slice_cnt, toString, trimToSize, var_info_iterator, var_names, views_iterator, vis_order_ok, worthDerivingFrom |
ppts
public List<PptTopLevel> ppts
- List of ppts that make up this combined ppt
rvars
public Map<String,String> rvars
- Map from the name of a redundant variable to its leader (the earliest
executed variable with guaranteed statically to have the same value).
dkconfig_asm_path_name
public static String dkconfig_asm_path_name
- If non-null, we will compute redundant binary variables
when creating a CombinedProgramPoint, using
the assembly information in the file specified.
dkconfig_rvars_file
public static String dkconfig_rvars_file
- If redundant variables are being computed, the results
of the redundancy analysis are printed to this stream.
See dkconfig_asm_path_name above.
PptCombined
public PptCombined(List<PptTopLevel> ppts,
PptCombined.CombinedVisResults vis)
findIntermediateBlocks
public static List<PptTopLevel> findIntermediateBlocks(PptTopLevel dest,
PptTopLevel source)
add_combined
public void add_combined()
- Add the current sample. The last samples for each of the program
points that make up the combined program point must have been added
to their last_values field.
combine_func_ppts
public static void combine_func_ppts(PptMap all_ppts,
List<PptTopLevel> func_ppts)
- Creates combined program points that cover multiple basic blocks.
Given a list of basic block ppts, each one is made into a combined
program point along with any basic blocks that pre-dominate it (always
execute previously to it).
The input is a list of the basic block ppts that make up the
function. The first element in the list is the function entry.
In each bb ppt, the field ppt_successors contains a list of the names
of all of the basic blocks that directly succeed it. That list
is used to calculate the dominators.
The resulting combined ppt has samples added to it when its
'trigger' ppt is executed. The trigger is always the last ppt in
the combined program point. The trigger is thus dominated by all
of the other basic blocks in the combined ppt. That guarantees
that samples for those basic blocks were received before the
trigger. Those samples are just saved away when they are
received. When the trigger ppt is executed, its samples are
combined with the samples from the other (previously executed)
basic blocks and the combined sample is processed by the combined
program point.
It is not necessary to create a unique combined program point for
each basic block. Consider two basic blocks (A and B). If A is
a pre-dominator of B, A will be included in B's combined program
point. If A is post-dominated by B, it can share B's combined
program point (because the combined program point for B will have
seen all of the samples for A). We say that A is 'subsumed by'
B.
Each program point (referred to as P) in the function is
modified as follows:
- P's combined_ppts_init flag is set to true.
- P's combined_ppt field is set to point to the (newly created)
combined ppt that will contain its invariants. The trigger for that
combined ppt is P's last postdominator that P predominates (which
may be P itself). This
combined ppt must see all of the samples for P. That implies that
the trigger for the combined ppt must post-dominate P. This is
obviously true when P is the trigger.
- If P is not the trigger, its combined_subsumed boolean field is
set to true.
Invariants over P:
P.combined_ppt != null
P.combined_subsumed==true implies
P.combined_ppt.trigger post-dominates P
P.combine_subsumed==false implies
P.combined_ppt.trigger == P
Invariants over the combined ppt C:
C.ppts[i] pre-dominates C.ppts[i+1]
trigger = C.ppts[sizeof(C.ppts)-1]
trigger.combine_subsumed==false;
trigger.combined_ppt == C
for (P : C.ppts[0..sizeof(C.ppts)-2])
P.combined_subsumed==false implies P.combined_ppt != C
P.combined_ppt == C implies Trigger post-dominates P
Note that trigger is not an actual field of PptCombined (though it
could be). But it should always be the last ppt in the list of
ppts in the combined ppt:
trigger = PptCombined.ppts.get(PptCombined.ppts.size()-1)
check
public boolean check()
- Checks the combined program point for correctness. Returns true
if all is well. Prints messages preceeded with 'ERROR' to stdout
and returns false on errors.
check_func_ppts
public static boolean check_func_ppts(List<PptTopLevel> ppts)
- Checks all of the ppts in a function for validity after combined
program points are created. Only performs checks that can't be
done in check. Returns true if all is well. Prints messages
preceeded with 'ERROR' to stdout and returns false on errors.
dump
public void dump()
- Dumps out the basic blocks that make up this combined ppt
dump
public static void dump(List<PptTopLevel> ppts)
- Dumps out the basic blocks in the list
short_name
public String short_name()
short_component_str
public String short_component_str()
- Returns a list of the component ppts that make up this combined ppt
short_component_str
public static String short_component_str(List<PptTopLevel> ppts)
- Returns a list of the component ppts that make up this combined ppt
bb_short_name
public static String bb_short_name(PptTopLevel ppt)
main
public static void main(String[] args)
throws IOException
- Throws:
IOException
redundantVarsTest
public static int redundantVarsTest(PptMap all_ppts)