daisytuner / sdfglib / 15656007340

coverage: 13.234% (-49.9%) from 63.144%
15656007340

Pull #76

github

web-flow 
Merge 9586c8161 into 413c53212
Pull Request #76: New Loop Dependency Analysis

361 of 465 new or added lines in 7 files covered. (77.63%)

6215 existing lines in 110 files now uncovered.

1612 of 12181 relevant lines covered (13.23%)

13.64 hits per line

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

0.0
/src/analysis/data_parallelism_analysis.cpp
1 
#include "sdfg/analysis/data_parallelism_analysis.h"
2 









3



#include <regex>










4












5



#include "sdfg/analysis/assumptions_analysis.h"










6



#include "sdfg/analysis/loop_analysis.h"










7



#include "sdfg/analysis/users.h"










8



#include "sdfg/codegen/language_extensions/cpp_language_extension.h"










9



#include "sdfg/structured_control_flow/structured_loop.h"










10












11



namespace sdfg {










12



namespace analysis {










13













UNCOV

14



std::pair<data_flow::Subset, data_flow::Subset> DataParallelismAnalysis::substitution(




×







15



    const data_flow::Subset& subset1, const data_flow::Subset& subset2, const std::string& indvar,










16



    const std::unordered_set<std::string>& moving_symbols, symbolic::ExpressionMap& replacements,










17



    std::vector<std::string>& substitions) {











UNCOV

18



    data_flow::Subset subset1_new;




×








UNCOV

19



    for (auto& dim : subset1) {




×








UNCOV

20



        auto args = dim->get_args();




×








UNCOV

21



        auto new_dim = dim;




×








UNCOV

22



        for (auto& arg : args) {




×








UNCOV

23



            if (!SymEngine::is_a<SymEngine::Symbol>(*arg) &&




×








UNCOV

24



                !SymEngine::is_a<SymEngine::Integer>(*arg)) {




×








UNCOV

25



                bool is_moving = false;




×








UNCOV

26



                for (auto& atom : symbolic::atoms(arg)) {




×








UNCOV

27



                    auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);




×








UNCOV

28



                    if (moving_symbols.find(sym->get_name()) != moving_symbols.end()) {




×








UNCOV

29



                        is_moving = true;




×








UNCOV

30



                        break;




×







31



                    }











UNCOV

32



                }




×








UNCOV

33



                if (!is_moving) {




×








UNCOV

34



                    if (replacements.find(arg) != replacements.end()) {




×







35



                        new_dim = symbolic::subs(new_dim, arg, replacements.at(arg));




×







36



                    } else {




×








UNCOV

37



                        auto repl = symbolic::symbol("c_" + std::to_string(replacements.size()));




×








UNCOV

38



                        substitions.push_back(repl->get_name());




×








UNCOV

39



                        replacements.insert({arg, repl});




×








UNCOV

40



                        new_dim = symbolic::subs(new_dim, arg, repl);




×








UNCOV

41



                    }




×








UNCOV

42



                }




×








UNCOV

43



            }




×







44



        }











UNCOV

45



        subset1_new.push_back(new_dim);




×








UNCOV

46



    }




×







47













UNCOV

48



    data_flow::Subset subset2_new;




×








UNCOV

49



    for (auto& dim : subset2) {




×








UNCOV

50



        auto args = dim->get_args();




×








UNCOV

51



        auto new_dim = dim;




×








UNCOV

52



        for (auto& arg : args) {




×








UNCOV

53



            if (!SymEngine::is_a<SymEngine::Symbol>(*arg) &&




×








UNCOV

54



                !SymEngine::is_a<SymEngine::Integer>(*arg)) {




×








UNCOV

55



                bool is_moving = false;




×








UNCOV

56



                for (auto& atom : symbolic::atoms(arg)) {




×








UNCOV

57



                    auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);




×








UNCOV

58



                    if (moving_symbols.find(sym->get_name()) != moving_symbols.end()) {




×








UNCOV

59



                        is_moving = true;




×








UNCOV

60



                        break;




×







61



                    }











UNCOV

62



                }




×








UNCOV

63



                if (!is_moving) {




×








UNCOV

64



                    if (replacements.find(arg) != replacements.end()) {




×








UNCOV

65



                        new_dim = symbolic::subs(new_dim, arg, replacements.at(arg));




×








UNCOV

66



                    } else {




×







67



                        auto repl = symbolic::symbol("c_" + std::to_string(replacements.size()));




×







68



                        substitions.push_back(repl->get_name());




×







69



                        replacements.insert({arg, repl});




×







70



                        new_dim = symbolic::subs(new_dim, arg, repl);




×







71



                    }




×








UNCOV

72



                }




×








UNCOV

73



            }




×







74



        }











UNCOV

75



        subset2_new.push_back(new_dim);




×








UNCOV

76



    }




×







77













UNCOV

78



    return {subset1_new, subset2_new};




×








UNCOV

79



};




×







80













UNCOV

81



std::pair<data_flow::Subset, data_flow::Subset> DataParallelismAnalysis::delinearization(




×







82



    const data_flow::Subset& subset1, const data_flow::Subset& subset2,










83



    const std::unordered_set<std::string>& moving_symbols,










84



    const symbolic::Assumptions& assumptions) {










85



    // Attempt to prove:










86



    // dim = i + j * M










87



    // We can delinearize iff:










88



    // 1. M is a constant










89



    // 2. i and j are not symbols










90



    // 3. M >= ub(i)











UNCOV

91



    data_flow::Subset subset1_new;




×








UNCOV

92



    for (auto& dim : subset1) {




×








UNCOV

93



        if (!SymEngine::is_a<SymEngine::Add>(*dim)) {




×








UNCOV

94



            subset1_new.push_back(dim);




×








UNCOV

95



            continue;




×







96



        }











UNCOV

97



        auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(dim);




×








UNCOV

98



        if (add->get_args().size() != 2) {




×








UNCOV

99



            subset1_new.push_back(dim);




×








UNCOV

100



            continue;




×







101



        }











UNCOV

102



        auto offset = add->get_args()[0];




×








UNCOV

103



        auto mult = add->get_args()[1];




×








UNCOV

104



        if (!SymEngine::is_a<SymEngine::Mul>(*mult)) {




×








UNCOV

105



            auto tmp = offset;




×








UNCOV

106



            offset = mult;




×








UNCOV

107



            mult = tmp;




×








UNCOV

108



        }




×








UNCOV

109



        if (!SymEngine::is_a<SymEngine::Mul>(*mult)) {




×








UNCOV

110



            subset1_new.push_back(dim);




×








UNCOV

111



            continue;




×







112



        }










113












114



        // Offset must be a symbol and moving











UNCOV

115



        if (!SymEngine::is_a<SymEngine::Symbol>(*offset)) {




×







116



            subset1_new.push_back(dim);




×







117



            continue;




×







118



        }











UNCOV

119



        auto off = SymEngine::rcp_static_cast<const SymEngine::Symbol>(offset);




×








UNCOV

120



        if (moving_symbols.find(off->get_name()) == moving_symbols.end()) {




×







121



            subset1_new.push_back(dim);




×







122



            continue;




×







123



        }










124












125



        // Multiplier must be two symbols and one moving











UNCOV

126



        auto mult_ = SymEngine::rcp_static_cast<const SymEngine::Mul>(mult);




×








UNCOV

127



        if (mult_->get_args().size() != 2) {




×







128



            subset1_new.push_back(dim);




×







129



            continue;




×







130



        }











UNCOV

131



        auto multiplier = mult_->get_args()[0];




×








UNCOV

132



        auto indvar_ = mult_->get_args()[1];




×








UNCOV

133



        if (!SymEngine::is_a<SymEngine::Symbol>(*multiplier) ||




×








UNCOV

134



            !SymEngine::is_a<SymEngine::Symbol>(*indvar_)) {




×







135



            subset1_new.push_back(dim);




×







136



            continue;




×







137



        }











UNCOV

138



        auto mul = SymEngine::rcp_static_cast<const SymEngine::Symbol>(multiplier);




×








UNCOV

139



        auto indvar = SymEngine::rcp_static_cast<const SymEngine::Symbol>(indvar_);




×








UNCOV

140



        if (moving_symbols.find(mul->get_name()) != moving_symbols.end()) {




×








UNCOV

141



            auto tmp = mul;




×








UNCOV

142



            mul = indvar;




×








UNCOV

143



            indvar = tmp;




×








UNCOV

144



        }




×








UNCOV

145



        if (moving_symbols.find(mul->get_name()) != moving_symbols.end() ||




×








UNCOV

146



            moving_symbols.find(indvar->get_name()) == moving_symbols.end()) {




×







147



            subset1_new.push_back(dim);




×







148



            continue;




×







149



        }










150













UNCOV

151



        bool is_nonnegative = false;




×








UNCOV

152



        symbolic::ExpressionSet lbs_off;




×








UNCOV

153



        symbolic::lower_bounds(off, assumptions, lbs_off);




×








UNCOV

154



        for (auto& lb : lbs_off) {




×








UNCOV

155



            if (SymEngine::is_a<SymEngine::Integer>(*lb)) {




×








UNCOV

156



                auto lb_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(lb);




×








UNCOV

157



                if (lb_int->as_int() >= 0) {




×








UNCOV

158



                    is_nonnegative = true;




×








UNCOV

159



                    break;




×







160



                }











UNCOV

161



            }




×







162



        }











UNCOV

163



        if (!is_nonnegative) {




×








UNCOV

164



            subset1_new.push_back(dim);




×








UNCOV

165



            continue;




×







166



        }










167













UNCOV

168



        bool success = false;




×








UNCOV

169



        symbolic::ExpressionSet ubs_off;




×








UNCOV

170



        symbolic::upper_bounds(off, assumptions, ubs_off);




×








UNCOV

171



        for (auto& ub_off : ubs_off) {




×








UNCOV

172



            if (symbolic::eq(mul, symbolic::add(ub_off, symbolic::one()))) {




×








UNCOV

173



                subset1_new.push_back(indvar);




×








UNCOV

174



                subset1_new.push_back(off);




×







175













UNCOV

176



                success = true;




×








UNCOV

177



                break;




×







178



            }










179



        }











UNCOV

180



        if (success) {




×








UNCOV

181



            continue;




×







182



        }











UNCOV

183



        subset1_new.push_back(dim);




×








UNCOV

184



    }




×







185













UNCOV

186



    data_flow::Subset subset2_new;




×








UNCOV

187



    for (auto& dim : subset2) {




×








UNCOV

188



        if (!SymEngine::is_a<SymEngine::Add>(*dim)) {




×








UNCOV

189



            subset2_new.push_back(dim);




×








UNCOV

190



            continue;




×







191



        }











UNCOV

192



        auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(dim);




×








UNCOV

193



        if (add->get_args().size() != 2) {




×








UNCOV

194



            subset2_new.push_back(dim);




×








UNCOV

195



            continue;




×







196



        }











UNCOV

197



        auto offset = add->get_args()[0];




×








UNCOV

198



        auto mult = add->get_args()[1];




×








UNCOV

199



        if (!SymEngine::is_a<SymEngine::Mul>(*mult)) {




×








UNCOV

200



            auto tmp = offset;




×








UNCOV

201



            offset = mult;




×








UNCOV

202



            mult = tmp;




×








UNCOV

203



        }




×








UNCOV

204



        if (!SymEngine::is_a<SymEngine::Mul>(*mult)) {




×








UNCOV

205



            subset2_new.push_back(dim);




×








UNCOV

206



            continue;




×







207



        }










208












209



        // Offset must be a symbol and moving











UNCOV

210



        if (!SymEngine::is_a<SymEngine::Symbol>(*offset)) {




×







211



            subset2_new.push_back(dim);




×







212



            continue;




×







213



        }











UNCOV

214



        auto off = SymEngine::rcp_static_cast<const SymEngine::Symbol>(offset);




×








UNCOV

215



        if (moving_symbols.find(off->get_name()) == moving_symbols.end()) {




×







216



            subset2_new.push_back(dim);




×







217



            continue;




×







218



        }










219












220



        // Multiplier must be two symbols and one moving











UNCOV

221



        auto mult_ = SymEngine::rcp_static_cast<const SymEngine::Mul>(mult);




×








UNCOV

222



        if (mult_->get_args().size() != 2) {




×







223



            subset2_new.push_back(dim);




×







224



            continue;




×







225



        }











UNCOV

226



        auto multiplier = mult_->get_args()[0];




×








UNCOV

227



        auto indvar_ = mult_->get_args()[1];




×








UNCOV

228



        if (!SymEngine::is_a<SymEngine::Symbol>(*multiplier) ||




×








UNCOV

229



            !SymEngine::is_a<SymEngine::Symbol>(*indvar_)) {




×







230



            subset2_new.push_back(dim);




×







231



            continue;




×







232



        }











UNCOV

233



        auto mul = SymEngine::rcp_static_cast<const SymEngine::Symbol>(multiplier);




×








UNCOV

234



        auto indvar = SymEngine::rcp_static_cast<const SymEngine::Symbol>(indvar_);




×








UNCOV

235



        if (moving_symbols.find(mul->get_name()) != moving_symbols.end()) {




×








UNCOV

236



            auto tmp = mul;




×








UNCOV

237



            mul = indvar;




×








UNCOV

238



            indvar = tmp;




×








UNCOV

239



        }




×








UNCOV

240



        if (moving_symbols.find(mul->get_name()) != moving_symbols.end() ||




×








UNCOV

241



            moving_symbols.find(indvar->get_name()) == moving_symbols.end()) {




×







242



            subset2_new.push_back(dim);




×







243



            continue;




×







244



        }










245













UNCOV

246



        bool is_nonnegative = false;




×








UNCOV

247



        symbolic::ExpressionSet lbs_off;




×








UNCOV

248



        symbolic::lower_bounds(off, assumptions, lbs_off);




×








UNCOV

249



        for (auto& lb : lbs_off) {




×








UNCOV

250



            if (SymEngine::is_a<SymEngine::Integer>(*lb)) {




×








UNCOV

251



                auto lb_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(lb);




×








UNCOV

252



                if (lb_int->as_int() >= 0) {




×








UNCOV

253



                    is_nonnegative = true;




×








UNCOV

254



                    break;




×







255



                }











UNCOV

256



            }




×







257



        }











UNCOV

258



        if (!is_nonnegative) {




×








UNCOV

259



            subset2_new.push_back(dim);




×








UNCOV

260



            continue;




×







261



        }










262













UNCOV

263



        bool success = false;




×








UNCOV

264



        symbolic::ExpressionSet ubs_off;




×








UNCOV

265



        symbolic::upper_bounds(off, assumptions, ubs_off);




×








UNCOV

266



        for (auto& ub_off : ubs_off) {




×








UNCOV

267



            if (symbolic::eq(mul, symbolic::add(ub_off, symbolic::one()))) {




×








UNCOV

268



                subset2_new.push_back(indvar);




×








UNCOV

269



                subset2_new.push_back(off);




×







270













UNCOV

271



                success = true;




×








UNCOV

272



                break;




×







273



            }










274



        }











UNCOV

275



        if (success) {




×








UNCOV

276



            continue;




×







277



        }











UNCOV

278



        subset2_new.push_back(dim);




×








UNCOV

279



    }




×







280













UNCOV

281



    return {subset1_new, subset2_new};




×








UNCOV

282



};




×







283













UNCOV

284



bool DataParallelismAnalysis::disjoint(const data_flow::Subset& subset1,




×







285



                                       const data_flow::Subset& subset2, const std::string& indvar,










286



                                       const std::unordered_set<std::string>& moving_symbols,










287



                                       const symbolic::Assumptions& assumptions) {











UNCOV

288



    if (subset1.size() != subset2.size()) {




×







289



        return false;




×







290



    }










291













UNCOV

292



    codegen::CPPLanguageExtension language_extension;




×







293












294



    // Attempt to substitute complex constant expressions by parameters











UNCOV

295



    symbolic::ExpressionMap replacements;




×








UNCOV

296



    std::vector<std::string> substitions;




×








UNCOV

297



    auto [subset1_, subset2_] = DataParallelismAnalysis::substitution(




×








UNCOV

298



        subset1, subset2, indvar, moving_symbols, replacements, substitions);




×







299












300



    // Attempt to delinearize subsets











UNCOV

301



    auto [subset1_2, subset2_2] =




×








UNCOV

302



        DataParallelismAnalysis::delinearization(subset1_, subset2_, moving_symbols, assumptions);




×







303












304



    // Overapproximate multiplications with parameters











UNCOV

305



    data_flow::Subset subset1_new;




×








UNCOV

306



    for (auto& dim : subset1_2) {




×








UNCOV

307



        auto dim_ = dim;




×








UNCOV

308



        for (auto mul : symbolic::muls(dim)) {




×








UNCOV

309



            auto mul_ = SymEngine::rcp_static_cast<const SymEngine::Mul>(mul);




×








UNCOV

310



            auto arg1 = mul_->get_args()[0];




×








UNCOV

311



            if (SymEngine::is_a<SymEngine::Symbol>(*arg1) &&




×








UNCOV

312



                moving_symbols.find(




×








UNCOV

313



                    SymEngine::rcp_static_cast<const SymEngine::Symbol>(arg1)->get_name()) ==




×








UNCOV

314



                    moving_symbols.end()) {




×







315



                dim_ = symbolic::subs(dim_, mul_, symbolic::one());




×







316



            } else {




×








UNCOV

317



                auto arg2 = mul_->get_args()[1];




×








UNCOV

318



                if (SymEngine::is_a<SymEngine::Symbol>(*arg2) &&




×








UNCOV

319



                    moving_symbols.find(




×








UNCOV

320



                        SymEngine::rcp_static_cast<const SymEngine::Symbol>(arg2)->get_name()) ==




×








UNCOV

321



                        moving_symbols.end()) {




×








UNCOV

322



                    dim_ = symbolic::subs(dim_, mul_, symbolic::one());




×








UNCOV

323



                }




×








UNCOV

324



            }




×








UNCOV

325



        }




×








UNCOV

326



        subset1_new.push_back(dim_);




×








UNCOV

327



    }




×








UNCOV

328



    data_flow::Subset subset2_new;




×








UNCOV

329



    for (auto& dim : subset2_2) {




×








UNCOV

330



        auto dim_ = dim;




×








UNCOV

331



        for (auto mul : symbolic::muls(dim)) {




×








UNCOV

332



            auto mul_ = SymEngine::rcp_static_cast<const SymEngine::Mul>(mul);




×








UNCOV

333



            auto arg1 = mul_->get_args()[0];




×








UNCOV

334



            if (SymEngine::is_a<SymEngine::Symbol>(*arg1) &&




×








UNCOV

335



                moving_symbols.find(




×








UNCOV

336



                    SymEngine::rcp_static_cast<const SymEngine::Symbol>(arg1)->get_name()) ==




×








UNCOV

337



                    moving_symbols.end()) {




×







338



                dim_ = symbolic::subs(dim_, mul_, symbolic::one());




×







339



            } else {




×








UNCOV

340



                auto arg2 = mul_->get_args()[1];




×








UNCOV

341



                if (SymEngine::is_a<SymEngine::Symbol>(*arg2) &&




×








UNCOV

342



                    moving_symbols.find(




×








UNCOV

343



                        SymEngine::rcp_static_cast<const SymEngine::Symbol>(arg2)->get_name()) ==




×








UNCOV

344



                        moving_symbols.end()) {




×








UNCOV

345



                    dim_ = symbolic::subs(dim_, mul_, symbolic::one());




×








UNCOV

346



                }




×








UNCOV

347



            }




×








UNCOV

348



        }




×








UNCOV

349



        subset2_new.push_back(dim_);




×








UNCOV

350



    }




×







351












352



    // Collect parameters and dimensions











UNCOV

353



    std::unordered_set<std::string> dimensions_;




×








UNCOV

354



    std::unordered_set<std::string> parameters_;




×








UNCOV

355



    for (auto& dim : subset1_new) {




×








UNCOV

356



        for (auto& atom : symbolic::atoms(dim)) {




×








UNCOV

357



            auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);




×








UNCOV

358



            if (sym->get_name() == indvar) {




×








UNCOV

359



                continue;




×







360



            }










361













UNCOV

362



            if (std::find(substitions.begin(), substitions.end(), sym->get_name()) !=




×








UNCOV

363



                substitions.end()) {




×








UNCOV

364



                continue;




×







365



            }











UNCOV

366



            if (moving_symbols.find(sym->get_name()) == moving_symbols.end()) {




×








UNCOV

367



                parameters_.insert(sym->get_name());




×








UNCOV

368



            } else {




×








UNCOV

369



                dimensions_.insert(sym->get_name());




×







370



            }











UNCOV

371



        }




×







372



    }











UNCOV

373



    for (auto& dim : subset2_new) {




×








UNCOV

374



        for (auto& atom : symbolic::atoms(dim)) {




×








UNCOV

375



            auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);




×








UNCOV

376



            if (sym->get_name() == indvar) {




×








UNCOV

377



                continue;




×







378



            }










379













UNCOV

380



            if (std::find(substitions.begin(), substitions.end(), sym->get_name()) !=




×








UNCOV

381



                substitions.end()) {




×








UNCOV

382



                continue;




×







383



            }











UNCOV

384



            if (moving_symbols.find(sym->get_name()) == moving_symbols.end()) {




×








UNCOV

385



                parameters_.insert(sym->get_name());




×








UNCOV

386



            } else {




×








UNCOV

387



                dimensions_.insert(sym->get_name());




×







388



            }











UNCOV

389



        }




×







390



    }











UNCOV

391



    dimensions_.insert(indvar);




×








UNCOV

392



    std::vector<std::string> dimensions;




×








UNCOV

393



    for (auto& dim : dimensions_) {




×








UNCOV

394



        dimensions.push_back(dim);




×







395



    }











UNCOV

396



    for (auto mv : moving_symbols) {




×








UNCOV

397



        if (dimensions_.find(mv) == dimensions_.end()) {




×








UNCOV

398



            dimensions.push_back(mv);




×








UNCOV

399



            dimensions_.insert(mv);




×








UNCOV

400



        }




×








UNCOV

401



    }




×








UNCOV

402



    std::vector<std::string> parameters;




×








UNCOV

403



    for (auto& dim : parameters_) {




×








UNCOV

404



        parameters.push_back(dim);




×







405



    }










406












407



    // Double dimension space and constraints











UNCOV

408



    size_t k = 0;




×








UNCOV

409



    std::vector<std::string> doubled_dimensions;




×








UNCOV

410



    std::vector<std::string> constraints;




×








UNCOV

411



    for (auto& dim : dimensions) {




×








UNCOV

412



        doubled_dimensions.push_back(dim + "_1");




×








UNCOV

413



        doubled_dimensions.push_back(dim + "_2");




×







414












415



        // Proof: dim_1 != dim_2











UNCOV

416



        if (dim == indvar) {




×








UNCOV

417



            constraints.push_back(dim + "_1 != " + dim + "_2");




×








UNCOV

418



        }




×







419












420



        // Collect lb and ub











UNCOV

421



        auto lb1 = assumptions.at(symbolic::symbol(dim)).lower_bound();




×








UNCOV

422



        for (auto atom : symbolic::atoms(lb1)) {




×








UNCOV

423



            auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);




×








UNCOV

424



            if (moving_symbols.find(sym->get_name()) == moving_symbols.end()) {




×








UNCOV

425



                if (parameters_.find(sym->get_name()) == parameters_.end()) {




×








UNCOV

426



                    parameters_.insert(sym->get_name());




×








UNCOV

427



                    parameters.push_back(sym->get_name());




×








UNCOV

428



                }




×








UNCOV

429



            }




×








UNCOV

430



        }




×








UNCOV

431



        auto ub1 = assumptions.at(symbolic::symbol(dim)).upper_bound();




×








UNCOV

432



        for (auto atom : symbolic::atoms(ub1)) {




×








UNCOV

433



            auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);




×








UNCOV

434



            if (moving_symbols.find(sym->get_name()) == moving_symbols.end()) {




×








UNCOV

435



                if (parameters_.find(sym->get_name()) == parameters_.end()) {




×








UNCOV

436



                    parameters_.insert(sym->get_name());




×








UNCOV

437



                    parameters.push_back(sym->get_name());




×








UNCOV

438



                }




×








UNCOV

439



            }




×








UNCOV

440



        }




×







441












442



        // Add constraints











UNCOV

443



        auto lb2 = lb1;




×








UNCOV

444



        auto ub2 = ub1;




×








UNCOV

445



        for (auto& dim : dimensions) {




×








UNCOV

446



            lb1 = symbolic::subs(lb1, symbolic::symbol(dim), symbolic::symbol(dim + "_1"));




×








UNCOV

447



            ub1 = symbolic::subs(ub1, symbolic::symbol(dim), symbolic::symbol(dim + "_1"));




×








UNCOV

448



            lb2 = symbolic::subs(lb2, symbolic::symbol(dim), symbolic::symbol(dim + "_2"));




×








UNCOV

449



            ub2 = symbolic::subs(ub2, symbolic::symbol(dim), symbolic::symbol(dim + "_2"));




×







450



        }










451













UNCOV

452



        if (!SymEngine::eq(*lb1, *symbolic::infty(-1))) {




×








UNCOV

453



            auto mins = SymEngine::atoms<const SymEngine::Min>(*lb1);




×








UNCOV

454



            if (mins.size() > 0) {




×







455



                continue;




×







456



            }










457













UNCOV

458



            if (SymEngine::is_a<SymEngine::Max>(*lb1)) {




×







459



                auto max = SymEngine::rcp_static_cast<const SymEngine::Max>(lb1);




×







460



                auto args1 = max->get_args();




×







461



                constraints.push_back(language_extension.expression(args1[0]) + " <= " + dim +




×







462



                                      "_1");










463



                constraints.push_back(language_extension.expression(args1[1]) + " <= " + dim +




×







464



                                      "_1");










465












466



                auto max_ = SymEngine::rcp_static_cast<const SymEngine::Max>(lb2);




×







467



                auto args2 = max_->get_args();




×







468



                constraints.push_back(language_extension.expression(args2[0]) + " <= " + dim +




×







469



                                      "_2");










470



                constraints.push_back(language_extension.expression(args2[1]) + " <= " + dim +




×







471



                                      "_2");










472



            } else {




×








UNCOV

473



                constraints.push_back(language_extension.expression(lb1) + " <= " + dim + "_1");




×








UNCOV

474



                constraints.push_back(language_extension.expression(lb2) + " <= " + dim + "_2");




×







475



            }











UNCOV

476



        }




×








UNCOV

477



        if (!SymEngine::eq(*ub1, *symbolic::infty(1))) {




×








UNCOV

478



            auto maxs = SymEngine::atoms<const SymEngine::Max>(*ub1);




×








UNCOV

479



            if (maxs.size() > 0) {




×







480



                continue;




×







481



            }










482













UNCOV

483



            if (SymEngine::is_a<SymEngine::Min>(*ub1)) {




×








UNCOV

484



                auto min = SymEngine::rcp_static_cast<const SymEngine::Min>(ub1);




×








UNCOV

485



                auto args1 = min->get_args();




×








UNCOV

486



                constraints.push_back(dim + "_1 <= " + language_extension.expression(args1[0]));




×








UNCOV

487



                constraints.push_back(dim + "_1 <= " + language_extension.expression(args1[1]));




×







488













UNCOV

489



                auto min_ = SymEngine::rcp_static_cast<const SymEngine::Min>(ub2);




×








UNCOV

490



                auto args2 = min_->get_args();




×








UNCOV

491



                constraints.push_back(dim + "_2 <= " + language_extension.expression(args2[0]));




×








UNCOV

492



                constraints.push_back(dim + "_2 <= " + language_extension.expression(args2[1]));




×








UNCOV

493



            } else {




×








UNCOV

494



                constraints.push_back(dim + "_1 <= " + language_extension.expression(ub1));




×








UNCOV

495



                constraints.push_back(dim + "_2 <= " + language_extension.expression(ub2));




×







496



            }











UNCOV

497



        }




×







498












499



        // Add map constraints











UNCOV

500



        auto map = assumptions.at(symbolic::symbol(dim)).map();




×








UNCOV

501



        if (map == SymEngine::null) {




×








UNCOV

502



            continue;




×







503



        }










504



        if (!SymEngine::is_a<SymEngine::Add>(*map)) {




×







505



            continue;




×







506



        }










507



        auto args = SymEngine::rcp_static_cast<const SymEngine::Add>(map)->get_args();




×







508



        if (args.size() != 2) {




×







509



            continue;




×







510



        }










511



        auto arg0 = args[0];




×







512



        auto arg1 = args[1];




×







513



        if (!symbolic::eq(arg0, symbolic::symbol(dim))) {




×







514



            arg0 = args[1];




×







515



            arg1 = args[0];




×







516



        }




×







517



        if (!symbolic::eq(arg0, symbolic::symbol(dim))) {




×







518



            continue;




×







519



        }










520



        if (!SymEngine::is_a<SymEngine::Integer>(*arg1)) {




×







521



            continue;




×







522



        }










523



        if (!SymEngine::is_a<SymEngine::Integer>(*lb1)) {




×







524



            continue;




×







525



        }










526












527



        std::string new_k = "__daisy_iterator" + std::to_string(k++);




×







528












529



        std::string k_1 = new_k + "_1";




×







530



        constraints.push_back("exists " + k_1 + " : " + dim +




×







531



                              "_1 = " + language_extension.expression(lb1) + " + " + k_1 + " * " +




×







532



                              language_extension.expression(arg1));




×







533












534



        std::string k_2 = new_k + "_2";




×







535



        constraints.push_back("exists " + k_2 + " : " + dim +




×







536



                              "_2 = " + language_extension.expression(lb1) + " + " + k_2 + " * " +




×







537



                              language_extension.expression(arg1));




×








UNCOV

538



    }




×







539












540



    // Extend parameters by dependening parameters











UNCOV

541



    size_t num_params = parameters.size();




×








UNCOV

542



    size_t num_params_old = 0;




×








UNCOV

543



    do {




×








UNCOV

544



        for (size_t i = 0; i < num_params; i++) {




×








UNCOV

545



            auto param = parameters[i];




×








UNCOV

546



            auto lb = assumptions.at(symbolic::symbol(param)).lower_bound();




×








UNCOV

547



            for (auto& atom : symbolic::atoms(lb)) {




×








UNCOV

548



                auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);




×








UNCOV

549



                if (moving_symbols.find(sym->get_name()) == moving_symbols.end()) {




×








UNCOV

550



                    if (parameters_.find(sym->get_name()) == parameters_.end()) {




×








UNCOV

551



                        parameters_.insert(sym->get_name());




×








UNCOV

552



                        parameters.push_back(sym->get_name());




×








UNCOV

553



                    }




×








UNCOV

554



                }




×








UNCOV

555



            }




×








UNCOV

556



            auto ub = assumptions.at(symbolic::symbol(param)).upper_bound();




×








UNCOV

557



            for (auto& atom : symbolic::atoms(ub)) {




×








UNCOV

558



                auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);




×








UNCOV

559



                if (moving_symbols.find(sym->get_name()) == moving_symbols.end()) {




×








UNCOV

560



                    if (parameters_.find(sym->get_name()) == parameters_.end()) {




×








UNCOV

561



                        parameters_.insert(sym->get_name());




×








UNCOV

562



                        parameters.push_back(sym->get_name());




×








UNCOV

563



                    }




×








UNCOV

564



                }




×








UNCOV

565



            }




×








UNCOV

566



        }




×








UNCOV

567



        num_params_old = num_params;




×








UNCOV

568



        num_params = parameters.size();




×








UNCOV

569



    } while (num_params != num_params_old);




×







570












571



    // Collect constraints for parameters











UNCOV

572



    for (size_t i = 0; i < parameters.size(); i++) {




×








UNCOV

573



        auto lb = assumptions.at(symbolic::symbol(parameters[i])).lower_bound();




×








UNCOV

574



        auto ub = assumptions.at(symbolic::symbol(parameters[i])).upper_bound();




×







575













UNCOV

576



        std::string constraint = "";




×








UNCOV

577



        if (!SymEngine::eq(*lb, *symbolic::infty(-1))) {




×








UNCOV

578



            if (SymEngine::is_a<SymEngine::Max>(*lb)) {




×







579



                auto max = SymEngine::rcp_static_cast<const SymEngine::Max>(lb);




×







580



                auto args = max->get_args();




×







581



                constraints.push_back(language_extension.expression(args[0]) +




×







582



                                      " <= " + parameters[i]);




×







583



                constraints.push_back(language_extension.expression(args[1]) +




×







584



                                      " <= " + parameters[i]);




×








UNCOV

585



            } else if (SymEngine::atoms<const SymEngine::Min>(*lb).size() > 0) {




×







586



            } else {




×








UNCOV

587



                constraints.push_back(language_extension.expression(lb) + " <= " + parameters[i]);




×







588



            }











UNCOV

589



        }




×








UNCOV

590



        if (!SymEngine::eq(*ub, *symbolic::infty(1))) {




×








UNCOV

591



            if (SymEngine::is_a<SymEngine::Min>(*ub)) {




×








UNCOV

592



                auto min = SymEngine::rcp_static_cast<const SymEngine::Min>(ub);




×








UNCOV

593



                auto args = min->get_args();




×








UNCOV

594



                constraints.push_back(parameters[i] +




×








UNCOV

595



                                      " <= " + language_extension.expression(args[0]));




×








UNCOV

596



                constraints.push_back(parameters[i] +




×








UNCOV

597



                                      " <= " + language_extension.expression(args[1]));




×








UNCOV

598



            } else if (SymEngine::atoms<const SymEngine::Max>(*ub).size() > 0) {




×







599



            } else {




×








UNCOV

600



                constraints.push_back(parameters[i] + " <= " + language_extension.expression(ub));




×







601



            }











UNCOV

602



        }




×








UNCOV

603



    }




×







604












605



    // Allocate context











UNCOV

606



    isl_ctx* ctx = isl_ctx_alloc();




×







607












608



    // Define maps











UNCOV

609



    std::string map_1;




×








UNCOV

610



    if (!parameters.empty()) {




×








UNCOV

611



        map_1 += "[";




×








UNCOV

612



        map_1 += helpers::join(parameters, ", ");




×








UNCOV

613



    }




×








UNCOV

614



    if (!substitions.empty()) {




×








UNCOV

615



        if (!parameters.empty()) {




×








UNCOV

616



            map_1 += ", ";




×








UNCOV

617



        } else {




×







618



            map_1 += "[";




×







619



        }











UNCOV

620



        map_1 += helpers::join(substitions, ", ");




×








UNCOV

621



    }




×








UNCOV

622



    if (!map_1.empty()) {




×








UNCOV

623



        map_1 += "] -> ";




×








UNCOV

624



    }




×








UNCOV

625



    map_1 += "{ [" + helpers::join(doubled_dimensions, ", ") + "] -> [";




×








UNCOV

626



    for (size_t i = 0; i < subset1_new.size(); i++) {




×








UNCOV

627



        auto dim = subset1_new[i];




×








UNCOV

628



        for (auto& iter : dimensions) {




×








UNCOV

629



            dim = symbolic::subs(dim, symbolic::symbol(iter), symbolic::symbol(iter + "_1"));




×







630



        }











UNCOV

631



        map_1 += language_extension.expression(dim);




×








UNCOV

632



        if (i < subset1_new.size() - 1) {




×








UNCOV

633



            map_1 += ", ";




×








UNCOV

634



        }




×








UNCOV

635



    }




×








UNCOV

636



    map_1 += "] : " + helpers::join(constraints, " and ") + " }";




×







637













UNCOV

638



    std::string map_2;




×








UNCOV

639



    if (!parameters.empty()) {




×








UNCOV

640



        map_2 += "[";




×








UNCOV

641



        map_2 += helpers::join(parameters, ", ");




×








UNCOV

642



    }




×








UNCOV

643



    if (!substitions.empty()) {




×








UNCOV

644



        if (!parameters.empty()) {




×








UNCOV

645



            map_2 += ", ";




×








UNCOV

646



        } else {




×







647



            map_2 += "[";




×







648



        }











UNCOV

649



        map_2 += helpers::join(substitions, ", ");




×








UNCOV

650



    }




×








UNCOV

651



    if (!map_2.empty()) {




×








UNCOV

652



        map_2 += "] -> ";




×








UNCOV

653



    }




×








UNCOV

654



    map_2 += "{ [" + helpers::join(doubled_dimensions, ", ") + "] -> [";




×








UNCOV

655



    for (size_t i = 0; i < subset2_new.size(); i++) {




×








UNCOV

656



        auto dim = subset2_new[i];




×








UNCOV

657



        for (auto& iter : dimensions) {




×








UNCOV

658



            dim = symbolic::subs(dim, symbolic::symbol(iter), symbolic::symbol(iter + "_2"));




×







659



        }











UNCOV

660



        map_2 += language_extension.expression(dim);




×








UNCOV

661



        if (i < subset2_new.size() - 1) {




×








UNCOV

662



            map_2 += ", ";




×








UNCOV

663



        }




×








UNCOV

664



    }




×








UNCOV

665



    map_2 += "] : " + helpers::join(constraints, " and ") + " }";




×







666












667



    // Replace NV symbols with names without .











UNCOV

668



    map_1 = std::regex_replace(map_1, std::regex("\\."), "_");




×








UNCOV

669



    map_2 = std::regex_replace(map_2, std::regex("\\."), "_");




×







670













UNCOV

671



    isl_map* index_map_1 = isl_map_read_from_str(ctx, map_1.c_str());




×








UNCOV

672



    if (!index_map_1) {




×







673



        isl_ctx_free(ctx);




×







674



        return false;




×







675



    }










676













UNCOV

677



    isl_map* index_map_2 = isl_map_read_from_str(ctx, map_2.c_str());




×








UNCOV

678



    if (!index_map_2) {




×







679



        isl_map_free(index_map_1);




×







680



        isl_ctx_free(ctx);




×







681



        return false;




×







682



    }










683













UNCOV

684



    isl_map* intersection = isl_map_intersect(index_map_1, index_map_2);




×








UNCOV

685



    if (!intersection) {




×







686



        isl_map_free(index_map_1);




×







687



        isl_map_free(index_map_2);




×







688



        isl_ctx_free(ctx);




×







689



        return false;




×







690



    }










691













UNCOV

692



    bool disjoint = isl_map_is_empty(intersection);




×







693













UNCOV

694



    isl_map_free(intersection);




×








UNCOV

695



    isl_ctx_free(ctx);




×







696













UNCOV

697



    return disjoint;




×








UNCOV

698



};




×







699













UNCOV

700



void DataParallelismAnalysis::classify(analysis::AnalysisManager& analysis_manager,




×







701



                                       structured_control_flow::StructuredLoop* loop) {











UNCOV

702



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




×







703












704



    // Strictly monotonic update











UNCOV

705



    auto& indvar = loop->indvar();




×








UNCOV

706



    if (!loop_analysis.is_monotonic(loop)) {




×








UNCOV

707



        this->results_.insert({loop, DataParallelismAnalysisResult()});




×








UNCOV

708



        return;




×







709



    }










710












711



    // Users analysis











UNCOV

712



    auto& body = loop->root();




×








UNCOV

713



    auto& users = analysis_manager.get<analysis::Users>();




×








UNCOV

714



    analysis::UsersView body_users(users, body);




×








UNCOV

715



    if (!body_users.views().empty() || !body_users.moves().empty()) {




×







716



        this->results_.insert({loop, DataParallelismAnalysisResult()});




×







717



        return;




×







718



    }










719













UNCOV

720



    this->results_.insert({loop, DataParallelismAnalysisResult()});




×








UNCOV

721



    auto& result = this->results_.at(loop);




×







722












723



    // Assumptions analysis











UNCOV

724



    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();




×








UNCOV

725



    auto assumptions = assumptions_analysis.get(body);




×







726












727



    // For each container, we now classify the access pattern










728












729



    // 1. Identify private containers











UNCOV

730



    auto locals = users.locals(sdfg_, body);




×








UNCOV

731



    for (auto& local : locals) {




×








UNCOV

732



        result.insert({local, Parallelism::PRIVATE});




×







733



    }










734












735



    // 2. Filter our read-only containers











UNCOV

736



    std::unordered_set<std::string> writeset;




×








UNCOV

737



    std::unordered_set<std::string> moving_symbols = {indvar->get_name()};




×








UNCOV

738



    for (auto& entry : body_users.writes()) {




×








UNCOV

739



        writeset.insert(entry->container());




×







740













UNCOV

741



        auto& type = sdfg_.type(entry->container());




×








UNCOV

742



        if (!dynamic_cast<const types::Scalar*>(&type)) {




×








UNCOV

743



            continue;




×







744



        }











UNCOV

745



        if (!types::is_integer(type.primitive_type())) {




×








UNCOV

746



            continue;




×







747



        }











UNCOV

748



        moving_symbols.insert(entry->container());




×







749



    }











UNCOV

750



    for (auto& entry : body_users.reads()) {




×








UNCOV

751



        if (writeset.find(entry->container()) != writeset.end()) {




×







752



            // Loop-carried dependencies in tasklets's conditions











UNCOV

753



            if (dynamic_cast<data_flow::Tasklet*>(entry->element())) {




×







754



                // Locals cannot be loop-carried











UNCOV

755



                if (locals.find(entry->container()) != locals.end()) {




×








UNCOV

756



                    continue;




×







757



                } else {











UNCOV

758



                    result.clear();




×








UNCOV

759



                    return;




×







760



                }










761



            }










762













UNCOV

763



            continue;




×







764



        }











UNCOV

765



        if (entry->container() == indvar->get_name()) {




×








UNCOV

766



            continue;




×







767



        }











UNCOV

768



        result.insert({entry->container(), Parallelism::READONLY});




×







769



    }










770












771



    // 3. Prove parallelism










772



    /** For each container of the writeset, we check the following properties:










773



     *  1. For all i, writes are disjoint (false -> empty parallelism)










774



     *  2. For all i, reads and writes are disjoint (false -> empty parallelism)










775



     */











UNCOV

776



    for (auto& container : writeset) {




×







777



        // Skip if already classified











UNCOV

778



        if (result.find(container) != result.end()) {




×








UNCOV

779



            continue;




×







780



        }










781












782



        // For each i1, i2, subset(i1) and subset(i2) are disjoint











UNCOV

783



        bool ww_conflict = false;




×








UNCOV

784



        auto writes = body_users.writes(container);




×








UNCOV

785



        for (auto& write : writes) {




×








UNCOV

786



            for (auto& write_ : writes) {




×








UNCOV

787



                if (write == write_ && writes.size() > 1) {




×








UNCOV

788



                    continue;




×







789



                }










790












791



                // Determine moving symbols locally











UNCOV

792



                std::unordered_set<std::string> moving_symbols_local = moving_symbols;




×







793













UNCOV

794



                auto subsets = write->subsets();




×








UNCOV

795



                auto subsets_ = write_->subsets();




×








UNCOV

796



                for (auto& subset : subsets) {




×








UNCOV

797



                    for (auto& subset_ : subsets_) {




×








UNCOV

798



                        if (!this->disjoint(subset, subset_, indvar->get_name(),




×







799



                                            moving_symbols_local, assumptions)) {











UNCOV

800



                            ww_conflict = true;




×








UNCOV

801



                            break;




×







802



                        }










803



                    }











UNCOV

804



                    if (ww_conflict) {




×








UNCOV

805



                        break;




×







806



                    }










807



                }











UNCOV

808



                if (ww_conflict) {




×








UNCOV

809



                    break;




×







810



                }











UNCOV

811



            }




×








UNCOV

812



            if (ww_conflict) {




×








UNCOV

813



                break;




×







814



            }










815



        }











UNCOV

816



        if (ww_conflict) {




×








UNCOV

817



            result.insert({container, Parallelism::DEPENDENT});




×








UNCOV

818



            continue;




×







819



        }










820













UNCOV

821



        bool rw_conflict = false;




×








UNCOV

822



        auto reads = body_users.reads(container);




×








UNCOV

823



        for (auto& read : reads) {




×








UNCOV

824



            for (auto& write_ : writes) {




×







825



                // Determine moving symbols locally











UNCOV

826



                std::unordered_set<std::string> moving_symbols_local = moving_symbols;




×







827













UNCOV

828



                auto subsets = read->subsets();




×








UNCOV

829



                auto subsets_ = write_->subsets();




×








UNCOV

830



                for (auto& subset : subsets) {




×








UNCOV

831



                    for (auto& subset_ : subsets_) {




×








UNCOV

832



                        if (!this->disjoint(subset, subset_, indvar->get_name(),




×







833



                                            moving_symbols_local, assumptions)) {











UNCOV

834



                            rw_conflict = true;




×








UNCOV

835



                            break;




×







836



                        }










837



                    }











UNCOV

838



                    if (rw_conflict) {




×








UNCOV

839



                        break;




×







840



                    }










841



                }











UNCOV

842



                if (rw_conflict) {




×








UNCOV

843



                    break;




×







844



                }











UNCOV

845



            }




×








UNCOV

846



            if (rw_conflict) {




×








UNCOV

847



                break;




×







848



            }










849



        }











UNCOV

850



        if (rw_conflict) {




×








UNCOV

851



            result.insert({container, Parallelism::DEPENDENT});




×








UNCOV

852



            continue;




×







853



        }










854













UNCOV

855



        result.insert({container, Parallelism::PARALLEL});




×








UNCOV

856



    }




×







857












858



    // 4. Reductions











UNCOV

859



    for (auto& entry : result) {




×








UNCOV

860



        auto& container = entry.first;




×








UNCOV

861



        auto& dep_type = entry.second;




×








UNCOV

862



        if (dep_type != Parallelism::DEPENDENT) {




×








UNCOV

863



            continue;




×







864



        }










865












866



        // Check if it is a reduction











UNCOV

867



        auto reads = body_users.reads(container);




×








UNCOV

868



        auto writes = body_users.writes(container);




×







869












870



        // Criterion: Must write to constant location











UNCOV

871



        bool is_reduction = true;




×








UNCOV

872



        auto first_write = writes.at(0);




×








UNCOV

873



        auto first_subset = first_write->subsets().at(0);




×








UNCOV

874



        for (auto& dim : first_subset) {




×








UNCOV

875



            for (auto& sym : moving_symbols) {




×








UNCOV

876



                if (symbolic::uses(dim, sym)) {




×








UNCOV

877



                    is_reduction = false;




×








UNCOV

878



                    break;




×







879



                }










880



            }











UNCOV

881



            if (!is_reduction) {




×








UNCOV

882



                break;




×







883



            }










884



        }











UNCOV

885



        if (!is_reduction) {




×








UNCOV

886



            continue;




×







887



        }










888












889



        // Criterion: All writes must have the same subset











UNCOV

890



        for (auto& write : writes) {




×








UNCOV

891



            for (auto& subset : write->subsets()) {




×








UNCOV

892



                if (subset.size() != first_subset.size()) {




×







893



                    is_reduction = false;




×







894



                    break;




×







895



                }










896













UNCOV

897



                for (size_t i = 0; i < subset.size(); i++) {




×








UNCOV

898



                    if (!symbolic::eq(subset[i], first_subset[i])) {




×







899



                        is_reduction = false;




×







900



                        break;




×







901



                    }











UNCOV

902



                }




×







903



            }










904



        }











UNCOV

905



        if (!is_reduction) {




×







906



            continue;




×







907



        }










908












909



        // Criterion: All reads must have the same subset











UNCOV

910



        for (auto& read : reads) {




×








UNCOV

911



            for (auto& subset : read->subsets()) {




×








UNCOV

912



                if (subset.size() != first_subset.size()) {




×







913



                    is_reduction = false;




×







914



                    break;




×







915



                }










916













UNCOV

917



                for (size_t i = 0; i < subset.size(); i++) {




×








UNCOV

918



                    if (!symbolic::eq(subset[i], first_subset[i])) {




×







919



                        is_reduction = false;




×







920



                        break;




×







921



                    }











UNCOV

922



                }




×







923



            }










924



        }










925













UNCOV

926



        if (is_reduction) {




×








UNCOV

927



            result[container] = Parallelism::REDUCTION;




×








UNCOV

928



        }




×








UNCOV

929



    }




×








UNCOV

930



};




×







931













UNCOV

932



void DataParallelismAnalysis::run(analysis::AnalysisManager& analysis_manager) {




×








UNCOV

933



    this->results_.clear();




×







934













UNCOV

935



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




×








UNCOV

936



    for (auto& loop : loop_analysis.loops()) {




×








UNCOV

937



        if (auto sloop = dynamic_cast<structured_control_flow::StructuredLoop*>(loop)) {




×








UNCOV

938



            this->classify(analysis_manager, sloop);




×








UNCOV

939



        }




×







940



    }











UNCOV

941



};




×







942













UNCOV

943



DataParallelismAnalysis::DataParallelismAnalysis(StructuredSDFG& sdfg)




×








UNCOV

944



    : Analysis(sdfg) {




×







945













UNCOV

946



      };




×







947













UNCOV

948



const DataParallelismAnalysisResult& DataParallelismAnalysis::get(




×







949



    const structured_control_flow::StructuredLoop& loop) const {











UNCOV

950



    return this->results_.at(&loop);




×







951



};










952













UNCOV

953



symbolic::Expression DataParallelismAnalysis::bound(




×







954



    const structured_control_flow::StructuredLoop& loop) {











UNCOV

955



    auto& indvar = loop.indvar();




×








UNCOV

956



    auto& condition = loop.condition();




×








UNCOV

957



    auto args = condition->get_args();




×








UNCOV

958



    if (args.size() != 2) {




×







959



        return SymEngine::null;




×







960



    }











UNCOV

961



    auto& arg0 = args[0];




×








UNCOV

962



    auto& arg1 = args[1];




×








UNCOV

963



    if (SymEngine::eq(*arg0, *indvar)) {




×








UNCOV

964



        return arg1;




×







965



    } else if (SymEngine::eq(*arg1, *indvar)) {




×







966



        return arg0;




×







967



    }










968



    return SymEngine::null;




×








UNCOV

969



};




×







970












971



}  // namespace analysis










972



}  // namespace sdfg























    

  • 

    •