dominators_test.cc File Reference

Tests for Lengauer-Tarjan dominator tree algorithm. More...

#include <gtest/gtest.h>
#include <chrono>
#include <cstdlib>
#include <string>
#include <random>
#include <Dominators.H>
#include <tpl_dynArray.H>
#include <tpl_dynMapTree.H>
#include <tpl_graph.H>

Include dependency graph for dominators_test.cc:

Go to the source code of this file.

Functions
	TEST (Dominators, SingleNode)
	TEST (Dominators, LinearChain)
	TEST (Dominators, DiamondGraph)
	TEST (Dominators, IfThenElseCFG)
	TEST (Dominators, LoopCFG)
	TEST (Dominators, ComplexTextbookCFG)
	TEST (Dominators, UnreachableNodes)
	TEST (Dominators, SelfLoop)
	TEST (Dominators, EmptyGraph)
	TEST (Dominators, ErrorHandlingNullRoot)
	TEST (Dominators, DominatorTreeStructure)
	TEST (Dominators, DominatorTreeLinearChain)
	TEST (Dominators, DominanceReflexive)
	TEST (Dominators, RootDominatesAll)
	TEST (Dominators, NonDominance)
	TEST (Dominators, DominanceFrontiersIfThenElse)
	TEST (Dominators, DominanceFrontiersLoop)
	TEST (Dominators, GetIdomSpecificNode)
	TEST (Dominators, GetIdomNullNodeThrows)
	TEST (Dominators, LargeRandomDAG)
	TEST (Dominators, PerformanceLargeRandomDAG)
	TEST (Dominators, OperatorAlias)
	TEST (Dominators, CacheReuse)
	TEST (Dominators, StringTypedGraph)
	TEST (PostDominators, SingleNode)
	TEST (PostDominators, LinearChain)
	TEST (PostDominators, DiamondGraph)
	TEST (PostDominators, IfThenElseCFG)
	TEST (PostDominators, LoopCFG)
	TEST (PostDominators, PostDominanceReflexive)
	TEST (PostDominators, ExitPostDominatesAll)
	TEST (PostDominators, PostDominanceFrontiers)
	TEST (PostDominators, PostDominatorTreeStructure)
	TEST (PostDominators, ErrorHandlingNullExit)

Detailed Description

Tests for Lengauer-Tarjan dominator tree algorithm.

Definition in file dominators_test.cc.

Function Documentation

TEST() [1/34]

TEST	(	Dominators	,
		CacheReuse
	)

Definition at line 645 of file dominators_test.cc.

References Aleph::divide_and_conquer_partition_dp(), nodes, and root().

TEST() [2/34]

TEST	(	Dominators	,
		ComplexTextbookCFG
	)

Definition at line 193 of file dominators_test.cc.

References Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), and m.

TEST() [3/34]

TEST	(	Dominators	,
		DiamondGraph
	)

Definition at line 116 of file dominators_test.cc.

References Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), m, and nodes.

TEST() [4/34]

TEST	(	Dominators	,
		DominanceFrontiersIfThenElse
	)

Definition at line 422 of file dominators_test.cc.

References Aleph::compute_dominance_frontiers(), Aleph::df(), Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [5/34]

TEST	(	Dominators	,
		DominanceFrontiersLoop
	)

Definition at line 457 of file dominators_test.cc.

References Aleph::compute_dominance_frontiers(), Aleph::df(), Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [6/34]

TEST	(	Dominators	,
		DominanceReflexive
	)

Definition at line 366 of file dominators_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [7/34]

TEST	(	Dominators	,
		DominatorTreeLinearChain
	)

Definition at line 345 of file dominators_test.cc.

References Aleph::build_dominator_tree(), Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [8/34]

TEST	(	Dominators	,
		DominatorTreeStructure
	)

Definition at line 311 of file dominators_test.cc.

References Aleph::build_dominator_tree(), Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [9/34]

TEST	(	Dominators	,
		EmptyGraph
	)

Definition at line 287 of file dominators_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [10/34]

TEST	(	Dominators	,
		ErrorHandlingNullRoot
	)

Definition at line 297 of file dominators_test.cc.

References Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [11/34]

TEST	(	Dominators	,
		GetIdomNullNodeThrows
	)

Definition at line 508 of file dominators_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [12/34]

TEST	(	Dominators	,
		GetIdomSpecificNode
	)

Definition at line 487 of file dominators_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [13/34]

TEST	(	Dominators	,
		IfThenElseCFG
	)

Definition at line 139 of file dominators_test.cc.

References Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), m, and nodes.

TEST() [14/34]

TEST	(	Dominators	,
		LargeRandomDAG
	)

Definition at line 523 of file dominators_test.cc.

References Aleph::build_dominator_tree(), Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), LocateFunctions< Container, Type >::get_it(), k, m, N, nodes, rng, and OhashCommon< HashTbl, Key >::size().

TEST() [15/34]

TEST	(	Dominators	,
		LinearChain
	)

Definition at line 96 of file dominators_test.cc.

References Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), m, and nodes.

TEST() [16/34]

TEST	(	Dominators	,
		LoopCFG
	)

Definition at line 166 of file dominators_test.cc.

References Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), m, and nodes.

TEST() [17/34]

TEST	(	Dominators	,
		NonDominance
	)

Definition at line 395 of file dominators_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [18/34]

TEST	(	Dominators	,
		OperatorAlias
	)

Definition at line 623 of file dominators_test.cc.

References Aleph::Lengauer_Tarjan_Dominators< GT, SA >::build_tree(), Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [19/34]

TEST	(	Dominators	,
		PerformanceLargeRandomDAG
	)

Definition at line 571 of file dominators_test.cc.

References Aleph::build_dominator_tree(), Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), k, m, N, nodes, rng, and OhashCommon< HashTbl, Key >::size().

TEST() [20/34]

TEST	(	Dominators	,
		RootDominatesAll
	)

Definition at line 380 of file dominators_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [21/34]

TEST	(	Dominators	,
		SelfLoop
	)

Definition at line 273 of file dominators_test.cc.

References Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), m, and nodes.

TEST() [22/34]

TEST	(	Dominators	,
		SingleNode
	)

Definition at line 84 of file dominators_test.cc.

References Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), m, nodes, and OhashCommon< HashTbl, Key >::size().

TEST() [23/34]

TEST	(	Dominators	,
		StringTypedGraph
	)

Definition at line 673 of file dominators_test.cc.

References Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), and m.

TEST() [24/34]

TEST	(	Dominators	,
		UnreachableNodes
	)

Definition at line 256 of file dominators_test.cc.

References Aleph::compute_dominators(), Aleph::divide_and_conquer_partition_dp(), m, nodes, Aleph::ODhashTable< Key, Cmp >::search(), and OhashCommon< HashTbl, Key >::size().

TEST() [25/34]

TEST	(	PostDominators	,
		DiamondGraph
	)

Definition at line 750 of file dominators_test.cc.

References Aleph::compute_post_dominators(), Aleph::divide_and_conquer_partition_dp(), m, and nodes.

TEST() [26/34]

TEST	(	PostDominators	,
		ErrorHandlingNullExit
	)

Definition at line 932 of file dominators_test.cc.

References Aleph::compute_post_dominators(), Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [27/34]

TEST	(	PostDominators	,
		ExitPostDominatesAll
	)

Definition at line 846 of file dominators_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [28/34]

TEST	(	PostDominators	,
		IfThenElseCFG
	)

Definition at line 773 of file dominators_test.cc.

References Aleph::compute_post_dominators(), Aleph::divide_and_conquer_partition_dp(), m, and nodes.

TEST() [29/34]

TEST	(	PostDominators	,
		LinearChain
	)

Definition at line 732 of file dominators_test.cc.

References Aleph::compute_post_dominators(), Aleph::divide_and_conquer_partition_dp(), m, and nodes.

TEST() [30/34]

TEST	(	PostDominators	,
		LoopCFG
	)

Definition at line 801 of file dominators_test.cc.

References Aleph::compute_post_dominators(), Aleph::divide_and_conquer_partition_dp(), m, and nodes.

TEST() [31/34]

TEST	(	PostDominators	,
		PostDominanceFrontiers
	)

Definition at line 862 of file dominators_test.cc.

References Aleph::compute_post_dominance_frontiers(), Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [32/34]

TEST	(	PostDominators	,
		PostDominanceReflexive
	)

Definition at line 831 of file dominators_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [33/34]

TEST	(	PostDominators	,
		PostDominatorTreeStructure
	)

Definition at line 905 of file dominators_test.cc.

References Aleph::build_post_dominator_tree(), Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [34/34]

TEST	(	PostDominators	,
		SingleNode
	)

Definition at line 720 of file dominators_test.cc.

References Aleph::compute_post_dominators(), Aleph::divide_and_conquer_partition_dp(), m, nodes, and OhashCommon< HashTbl, Key >::size().