26556322966

Committed 27 May 2026 03:45PM UTC coverage: 60.869% (-0.02%) from 60.886%

Build # 26556322966

Build Type

push

github

Committed by

web-flow

Commit Message

Libnode ptr edges (#719)

Migrating SDFGs to treat pointers as inputs to libNodes / Calls as scalars.
A pointer will only appear in an output edge if its actually returned from the function (like malloc).

* Stdlib, Blas and Tensor Matmul nodes were migrated to this new format. Other, currently transitory Tensor Nodes are not yet migrated.
* DOCC version was bumped to incorporate previous docc-llvm versions (up to 0.4.0) that had been counted separately.
! Until all passes consider the use / leak of pointers as uncertainty / hiding potential writes, TensorNodes are declared as general side-effect.
* Lots of utility functions to centralize the creation (and edges) of various libNodes that needed to be changed.
* Fixed & unified docc paths across python and llvm front-ends.
* Skip BlockFusion test that fails to its libNodes currently having side effects
~ Prevent a crash in DotViz when using symbolic offsets into structs
* Removing old ConstProp pass, it is not safe for the new pointer representation and should not be all too critical

Coverage Stats

961 of 1749 new or added lines in 52 files covered. (54.95%)

87 existing lines in 28 files now uncovered.

35225 of 57870 relevant lines covered (60.87%)

11046.32 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

53.66

/sdfg/src/passes/structured_control_flow/for2map.cpp

#include "sdfg/passes/structured_control_flow/for2map.h"

#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/loop_carried_dependency_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/passes/pipeline.h"

namespace sdfg {
namespace passes {

std::string For2MapPass::name() { return "For2Map"; }

bool For2MapPass::can_be_applied(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::For& for_stmt
) {
    if (!for_stmt.is_monotonic()) {
        return false;
    }

    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();

    if (loop_analysis.loop_info(&for_stmt).has_side_effects) {
        return false;
    }

    // Criterion: Loop must not have side-effecting body
    std::list<const structured_control_flow::ControlFlowNode*> queue = {&for_stmt.root()};
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();

        if (auto block = dynamic_cast<const structured_control_flow::Block*>(current)) {
            for (auto& node : block->dataflow().nodes()) {
                if (auto library_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {
                    if (library_node->side_effect()) {
                        return false;
                    }
                }
            }
        } else if (auto seq = dynamic_cast<const structured_control_flow::Sequence*>(current)) {
            for (size_t i = 0; i < seq->size(); i++) {
                auto& child = seq->at(i).first;
                queue.push_back(&child);
            }
        } else if (auto ifelse = dynamic_cast<const structured_control_flow::IfElse*>(current)) {
            for (size_t i = 0; i < ifelse->size(); i++) {
                auto& branch = ifelse->at(i).first;
                queue.push_back(&branch);
            }
        } else if (auto loop = dynamic_cast<const structured_control_flow::StructuredLoop*>(current)) {
            queue.push_back(&loop->root());
        } else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(current)) {
            queue.push_back(&while_stmt->root());
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Break*>(current)) {
            // Do nothing
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Continue*>(current)) {
            // Do nothing
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Return*>(current)) {
            return false;
        } else {
            throw InvalidSDFGException("Unknown control flow node type in For2Map pass.");
        }
    }

    // Criterion: loop must be data-parallel w.r.t containers
    auto& lcd = analysis_manager.get<analysis::LoopCarriedDependencyAnalysis>();
    auto& dependencies = lcd.dependencies(for_stmt);

    // a. No true dependencies (RAW) between iterations
    if (lcd.has_loop_carried_hazard(for_stmt)) {
        return false;
    }

    // b. False dependencies (WAW) are limited to loop-local variables
    auto& users = analysis_manager.get<analysis::Users>();
    analysis::UsersView body_users(users, for_stmt.root());
    auto locals = users.locals(for_stmt.root());
    for (auto& dep : dependencies) {
        auto& container = dep.first;
        auto& type = builder.subject().type(container);

        // Must be loop-local variable
        if (locals.find(container) == locals.end()) {
            // Special case: Constant scalar assignments
            if (type.type_id() == types::TypeID::Scalar) {
                auto writes = body_users.writes(container);
                auto reads = body_users.reads(container);
                if (writes.size() == 1 && reads.empty()) {
                    auto write = writes.front();
                    if (auto write_transition =
                            dynamic_cast<const structured_control_flow::Transition*>(write->element())) {
                        auto lhs = symbolic::symbol(container);
                        auto rhs = write_transition->assignments().at(lhs);
                        if (SymEngine::is_a<SymEngine::Integer>(*rhs)) {
                            continue;
                        }
                    }
                }
            }

            return false;
        }

        // Check for pointers that they point to loop-local storage
        if (type.type_id() != types::TypeID::Pointer) {
            continue;
        }
        if (type.storage_type().allocation() == types::StorageType::AllocationType::Managed) {
            continue;
        }

        // or alias of loop-local storage
        if (users.moves(container).size() != 1) {
            return false;
        }
        auto move = users.moves(container).front();
        auto move_node = static_cast<const data_flow::AccessNode*>(move->element());
        auto& move_graph = move_node->get_parent();
        auto& move_edge = *move_graph.in_edges(*move_node).begin();
        auto& move_src = static_cast<const data_flow::AccessNode&>(move_edge.src());
        if (locals.find(move_src.data()) == locals.end()) {
            return false;
        }
        auto& move_type = builder.subject().type(move_src.data());
        if (move_type.storage_type().allocation() == types::StorageType::AllocationType::Unmanaged) {
            return false;
        }
    }

    // c. indvar not used after for
    if (locals.find(for_stmt.indvar()->get_name()) != locals.end()) {
        return false;
    }

    return true;
}

bool For2MapPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto& loop_tree = loop_analysis.loop_tree();

    // Traverse loops in bottom-up fashion (reverse loop)
    std::list<structured_control_flow::For*> for_queue;
    for (auto& entry : loop_tree) {
        if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(entry.first)) {
            for_queue.push_front(for_stmt);
        }
    }

    // Mark for loops that can be converted
    std::list<structured_control_flow::For*> map_queue;
    for (auto& for_loop : for_queue) {
        if (this->can_be_applied(builder, analysis_manager, *for_loop)) {
            map_queue.push_back(for_loop);
        }
    }

    // Convert marked for loops
    bool applied = false;
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    for (auto& for_stmt : map_queue) {
        auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(for_stmt));
        builder.convert_for(*parent, *for_stmt);
        applied = true;
    }

    return applied;
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/for2map.h"
2
3	#include "sdfg/analysis/loop_analysis.h"
4	#include "sdfg/analysis/loop_carried_dependency_analysis.h"
5	#include "sdfg/analysis/scope_analysis.h"
6	#include "sdfg/analysis/users.h"
7	#include "sdfg/passes/pipeline.h"
8
9	namespace sdfg {
10	namespace passes {
11
12	std::string For2MapPass::name() { return "For2Map"; }	×
13
14	bool For2MapPass::can_be_applied(
15	builder::StructuredSDFGBuilder& builder,
16	analysis::AnalysisManager& analysis_manager,
17	structured_control_flow::For& for_stmt
18	) {	205✔
19	if (!for_stmt.is_monotonic()) {	205✔
20	return false;	×
21	}	×
22
23	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	205✔
24
25	if (loop_analysis.loop_info(&for_stmt).has_side_effects) {	205✔
NEW 26	return false;	×
NEW 27	}	×
28
29	// Criterion: Loop must not have side-effecting body
30	std::list<const structured_control_flow::ControlFlowNode*> queue = {&for_stmt.root()};	205✔
31	while (!queue.empty()) {	1,245✔
32	auto current = queue.front();	1,040✔
33	queue.pop_front();	1,040✔
34
35	if (auto block = dynamic_cast<const structured_control_flow::Block*>(current)) {	1,040✔
36	for (auto& node : block->dataflow().nodes()) {	1,970✔
37	if (auto library_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {	1,970✔
38	if (library_node->side_effect()) {	2✔
39	return false;	×
40	}	×
41	}	2✔
42	}	1,970✔
43	} else if (auto seq = dynamic_cast<const structured_control_flow::Sequence*>(current)) {	591✔
44	for (size_t i = 0; i < seq->size(); i++) {	1,040✔
45	auto& child = seq->at(i).first;	642✔
46	queue.push_back(&child);	642✔
47	}	642✔
48	} else if (auto ifelse = dynamic_cast<const structured_control_flow::IfElse*>(current)) {	398✔
49	for (size_t i = 0; i < ifelse->size(); i++) {	×
50	auto& branch = ifelse->at(i).first;	×
51	queue.push_back(&branch);	×
52	}	×
53	} else if (auto loop = dynamic_cast<const structured_control_flow::StructuredLoop*>(current)) {	193✔
54	queue.push_back(&loop->root());	193✔
55	} else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(current)) {	193✔
56	queue.push_back(&while_stmt->root());	×
57	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Break*>(current)) {	×
58	// Do nothing
59	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Continue*>(current)) {	×
60	// Do nothing
61	} else if (auto for_stmt = dynamic_cast<const structured_control_flow::Return*>(current)) {	×
62	return false;	×
63	} else {	×
64	throw InvalidSDFGException("Unknown control flow node type in For2Map pass.");	×
65	}	×
66	}	1,040✔
67
68	// Criterion: loop must be data-parallel w.r.t containers
69	auto& lcd = analysis_manager.get<analysis::LoopCarriedDependencyAnalysis>();	205✔
70	auto& dependencies = lcd.dependencies(for_stmt);	205✔
71
72	// a. No true dependencies (RAW) between iterations
73	if (lcd.has_loop_carried_hazard(for_stmt)) {	205✔
74	return false;	128✔
75	}	128✔
76
77	// b. False dependencies (WAW) are limited to loop-local variables
78	auto& users = analysis_manager.get<analysis::Users>();	77✔
79	analysis::UsersView body_users(users, for_stmt.root());	77✔
80	auto locals = users.locals(for_stmt.root());	77✔
81	for (auto& dep : dependencies) {	111✔
82	auto& container = dep.first;	111✔
83	auto& type = builder.subject().type(container);	111✔
84
85	// Must be loop-local variable
86	if (locals.find(container) == locals.end()) {	111✔
87	// Special case: Constant scalar assignments
88	if (type.type_id() == types::TypeID::Scalar) {	×
89	auto writes = body_users.writes(container);	×
90	auto reads = body_users.reads(container);	×
91	if (writes.size() == 1 && reads.empty()) {	×
92	auto write = writes.front();	×
93	if (auto write_transition =	×
94	dynamic_cast<const structured_control_flow::Transition*>(write->element())) {	×
95	auto lhs = symbolic::symbol(container);	×
96	auto rhs = write_transition->assignments().at(lhs);	×
97	if (SymEngine::is_a<SymEngine::Integer>(*rhs)) {	×
98	continue;	×
99	}	×
100	}	×
101	}	×
102	}	×
103
104	return false;	×
105	}	×
106
107	// Check for pointers that they point to loop-local storage
108	if (type.type_id() != types::TypeID::Pointer) {	111✔
109	continue;	111✔
110	}	111✔
111	if (type.storage_type().allocation() == types::StorageType::AllocationType::Managed) {	×
112	continue;	×
113	}	×
114
115	// or alias of loop-local storage
116	if (users.moves(container).size() != 1) {	×
117	return false;	×
118	}	×
119	auto move = users.moves(container).front();	×
120	auto move_node = static_cast<const data_flow::AccessNode*>(move->element());	×
121	auto& move_graph = move_node->get_parent();	×
122	auto& move_edge = move_graph.in_edges(move_node).begin();	×
123	auto& move_src = static_cast<const data_flow::AccessNode&>(move_edge.src());	×
124	if (locals.find(move_src.data()) == locals.end()) {	×
125	return false;	×
126	}	×
127	auto& move_type = builder.subject().type(move_src.data());	×
128	if (move_type.storage_type().allocation() == types::StorageType::AllocationType::Unmanaged) {	×
129	return false;	×
130	}	×
131	}	×
132
133	// c. indvar not used after for
134	if (locals.find(for_stmt.indvar()->get_name()) != locals.end()) {	77✔
135	return false;	×
136	}	×
137
138	return true;	77✔
139	}	77✔
140
141	bool For2MapPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	88✔
142	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	88✔
143	auto& loop_tree = loop_analysis.loop_tree();	88✔
144
145	// Traverse loops in bottom-up fashion (reverse loop)
146	std::list<structured_control_flow::For*> for_queue;	88✔
147	for (auto& entry : loop_tree) {	341✔
148	if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(entry.first)) {	341✔
149	for_queue.push_front(for_stmt);	205✔
150	}	205✔
151	}	341✔
152
153	// Mark for loops that can be converted
154	std::list<structured_control_flow::For*> map_queue;	88✔
155	for (auto& for_loop : for_queue) {	205✔
156	if (this->can_be_applied(builder, analysis_manager, *for_loop)) {	205✔
157	map_queue.push_back(for_loop);	77✔
158	}	77✔
159	}	205✔
160
161	// Convert marked for loops
162	bool applied = false;	88✔
163	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	88✔
164	for (auto& for_stmt : map_queue) {	88✔
165	auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(for_stmt));	77✔
166	builder.convert_for(parent, for_stmt);	77✔
167	applied = true;	77✔
168	}	77✔
169
170	return applied;	88✔
171	}	88✔
172
173	} // namespace passes
174	} // namespace sdfg

daisytuner / docc / 26556322966

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous