1421c0733fdb1780ad6fd23eefba78004528dacd2Lang Hames//===-- Solution.h ------- PBQP Solution ------------------------*- C++ -*-===// 2caaf120a676f493b1535c9facd188539bfad3f80Lang Hames// 3caaf120a676f493b1535c9facd188539bfad3f80Lang Hames// The LLVM Compiler Infrastructure 4caaf120a676f493b1535c9facd188539bfad3f80Lang Hames// 5caaf120a676f493b1535c9facd188539bfad3f80Lang Hames// This file is distributed under the University of Illinois Open Source 6caaf120a676f493b1535c9facd188539bfad3f80Lang Hames// License. See LICENSE.TXT for details. 7caaf120a676f493b1535c9facd188539bfad3f80Lang Hames// 8caaf120a676f493b1535c9facd188539bfad3f80Lang Hames//===----------------------------------------------------------------------===// 9caaf120a676f493b1535c9facd188539bfad3f80Lang Hames// 10030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames// PBQP Solution class. 11caaf120a676f493b1535c9facd188539bfad3f80Lang Hames// 12caaf120a676f493b1535c9facd188539bfad3f80Lang Hames//===----------------------------------------------------------------------===// 13caaf120a676f493b1535c9facd188539bfad3f80Lang Hames 146699fb27091927528f9f6059c3034d566dbed623Lang Hames#ifndef LLVM_CODEGEN_PBQP_SOLUTION_H 156699fb27091927528f9f6059c3034d566dbed623Lang Hames#define LLVM_CODEGEN_PBQP_SOLUTION_H 166699fb27091927528f9f6059c3034d566dbed623Lang Hames 17030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames#include "Graph.h" 18255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "Math.h" 19030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames#include <map> 206699fb27091927528f9f6059c3034d566dbed623Lang Hames 21030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hamesnamespace PBQP { 226699fb27091927528f9f6059c3034d566dbed623Lang Hames 23030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames /// \brief Represents a solution to a PBQP problem. 24030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames /// 25030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames /// To get the selection for each node in the problem use the getSelection method. 26030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames class Solution { 27030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames private: 287642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef std::map<GraphBase::NodeId, unsigned> SelectionsMap; 30030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames SelectionsMap selections; 31030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames 327642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions; 337642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames 34030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames public: 35030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames 36b76d20969f987cf18285bf8439d00444ce5aa6fbLang Hames /// \brief Initialise an empty solution. 37b76d20969f987cf18285bf8439d00444ce5aa6fbLang Hames Solution() 38b76d20969f987cf18285bf8439d00444ce5aa6fbLang Hames : r0Reductions(0), r1Reductions(0), r2Reductions(0), rNReductions(0) {} 39b76d20969f987cf18285bf8439d00444ce5aa6fbLang Hames 40030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames /// \brief Number of nodes for which selections have been made. 41030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames /// @return Number of nodes for which selections have been made. 42030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames unsigned numNodes() const { return selections.size(); } 43030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames 447642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// \brief Records a reduction via the R0 rule. Should be called from the 457642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// solver only. 467642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames void recordR0() { ++r0Reductions; } 477642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames 487642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// \brief Returns the number of R0 reductions applied to solve the problem. 497642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames unsigned numR0Reductions() const { return r0Reductions; } 507642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames 517642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// \brief Records a reduction via the R1 rule. Should be called from the 527642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// solver only. 537642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames void recordR1() { ++r1Reductions; } 547642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames 557642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// \brief Returns the number of R1 reductions applied to solve the problem. 567642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames unsigned numR1Reductions() const { return r1Reductions; } 577642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames 587642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// \brief Records a reduction via the R2 rule. Should be called from the 597642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// solver only. 607642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames void recordR2() { ++r2Reductions; } 617642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames 627642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// \brief Returns the number of R2 reductions applied to solve the problem. 637642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames unsigned numR2Reductions() const { return r2Reductions; } 647642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames 657642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// \brief Records a reduction via the RN rule. Should be called from the 667642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// solver only. 677642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames void recordRN() { ++ rNReductions; } 687642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames 697642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames /// \brief Returns the number of RN reductions applied to solve the problem. 707642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames unsigned numRNReductions() const { return rNReductions; } 717642572e6d5e3ca0c5d18e2591989bd5c4f4b31cLang Hames 72030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames /// \brief Set the selection for a given node. 73332cbf1d4503fcad3b5f3bf6ff73889feff03ad7NAKAMURA Takumi /// @param nodeId Node id. 74332cbf1d4503fcad3b5f3bf6ff73889feff03ad7NAKAMURA Takumi /// @param selection Selection for nodeId. 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void setSelection(GraphBase::NodeId nodeId, unsigned selection) { 76a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames selections[nodeId] = selection; 77030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames } 78030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames 79030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames /// \brief Get a node's selection. 80332cbf1d4503fcad3b5f3bf6ff73889feff03ad7NAKAMURA Takumi /// @param nodeId Node id. 81332cbf1d4503fcad3b5f3bf6ff73889feff03ad7NAKAMURA Takumi /// @return The selection for nodeId; 8236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getSelection(GraphBase::NodeId nodeId) const { 83a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames SelectionsMap::const_iterator sItr = selections.find(nodeId); 84030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames assert(sItr != selections.end() && "No selection for node."); 85030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames return sItr->second; 86030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames } 87030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames 88030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames }; 896699fb27091927528f9f6059c3034d566dbed623Lang Hames 906699fb27091927528f9f6059c3034d566dbed623Lang Hames} 916699fb27091927528f9f6059c3034d566dbed623Lang Hames 926699fb27091927528f9f6059c3034d566dbed623Lang Hames#endif // LLVM_CODEGEN_PBQP_SOLUTION_H 93