CGRAOmp::BalanceTree Class Reference

A DFGPass to balance the tree structure. More...

#include <BalanceTree.hpp>

Inheritance diagram for CGRAOmp::BalanceTree:

Public Member Functions
bool	run (CGRADFG &G, Loop &L, FunctionAnalysisManager &FAM, LoopAnalysisManager &LAM, LoopStandardAnalysisResults &AR)
	Apply tree height reduction for a given DFG. More...

Private Types
using	EdgeListTy = SmallVector< DFGEdge *, 10U >

Private Member Functions
void	initWeight (CGRADFG &G)
	Initialize the graph weight. More...
SmallVector< ComputeNode * >	findRootCandidates (CGRADFG &G)
	find candidates for root node More...
void	toBalanced (CGRADFG &G, ComputeNode *Root)
	Balance the graph for a given root node. More...

Static Private Member Functions
static int	getOperatorPrecedence (ComputeNode *N)
	Function to obtain the precedence for a given ComputeNode. More...

Private Attributes
DenseMap< DFGNode *, int >	weight
DenseMap< DFGNode *, bool >	visited
SmallPtrSet< DFGNode *, 10 >	candidate_set
bool	changed

Static Private Attributes
static std::map< int, int >	OperatorPrecedence
	map to decode operator precedence More...

Detailed Description

A DFGPass to balance the tree structure.

This optimization is based on algorithm proposed in [1].

See also

[1] Coons, Katherine Elizabeth, et al. Optimal huffman tree-height reduction for instruction-level parallelism. Computer Science Department, University of Texas at Austin, 2008.

Member Typedef Documentation

EdgeListTy

using CGRAOmp::BalanceTree::EdgeListTy = SmallVector<DFGEdge *, 10U>

private

Member Function Documentation

findRootCandidates()

SmallVector< ComputeNode * > BalanceTree::findRootCandidates ( CGRADFG &  G )

private

find candidates for root node

Parameters

G	Data flow graph to be balanced

Returns

SmallVector<ComputeNode*> a list of found candidates

getOperatorPrecedence()

static int CGRAOmp::BalanceTree::getOperatorPrecedence ( ComputeNode *  N )

inlinestaticprivate

Function to obtain the precedence for a given ComputeNode.

Parameters

N	the computational node

Returns

It returns integer of precedence level

initWeight()

void BalanceTree::initWeight ( CGRADFG &  G )

private

Initialize the graph weight.

Parameters

G	Data flow graph to be balanced

run()

bool BalanceTree::run	(	CGRADFG &	G,
		Loop &	L,
		FunctionAnalysisManager &	FAM,
		LoopAnalysisManager &	LAM,
		LoopStandardAnalysisResults &	AR
	)

Apply tree height reduction for a given DFG.

Parameters

G	Data flow graph (DFG)
L	Loop associated with the DFGs
FAM	FunctionAnalysisManager to access analysis results
LAM	LoopAnalysisManager to access analysis results
AR	LoopStandardAnalysisResults

Returns

It returns true if DFG G is changed

Otherwise, it returns false

toBalanced()

void BalanceTree::toBalanced ( CGRADFG &  G, ComputeNode *  Root  )

private

Balance the graph for a given root node.

Parameters

G	Data flow graph to be balanced
Root	Root node

Member Data Documentation

candidate_set

SmallPtrSet<DFGNode*, 10> CGRAOmp::BalanceTree::candidate_set

private

changed

bool CGRAOmp::BalanceTree::changed

private

OperatorPrecedence

map< int, int > BalanceTree::OperatorPrecedence

staticprivate

map to decode operator precedence

• key: Opcode of llvm::Instruction
• value: the level of precedence (int)

It is a similar setting to precedence table of clang But the lower level means the higher priority

See also

clang/Basic/OperatorPrecedence.h

visited

DenseMap<DFGNode*,bool> CGRAOmp::BalanceTree::visited

private

weight

DenseMap<DFGNode*,int> CGRAOmp::BalanceTree::weight

private

---

The documentation for this class was generated from the following files:

• include/BalanceTree.hpp
• src/Passes/CGRAOmpDFGPass/BalanceTree.cpp