1 ///////////////////////////////////////////////////////////////////////////////
2 // BSD 3-Clause License
3 //
4 // Copyright (c) 2019-2020, The Regents of the University of California
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 // * Redistributions of source code must retain the above copyright notice, this
11 //   list of conditions and the following disclaimer.
12 //
13 // * Redistributions in binary form must reproduce the above copyright notice,
14 //   this list of conditions and the following disclaimer in the documentation
15 //   and/or other materials provided with the distribution.
16 //
17 // * Neither the name of the copyright holder nor the names of its
18 //   contributors may be used to endorse or promote products derived from
19 //   this software without specific prior written permission.
20 //
21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 // ARE
25 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
26 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
28 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ///////////////////////////////////////////////////////////////////////////////
33 
34 #pragma once
35 
36 #include <map>
37 #include <set>
38 #include <unordered_map>
39 #include <vector>
40 
41 #include "mpl/Partition.h"
42 #include "opendb/db.h"
43 #include "sta/GraphClass.hh"
44 #include "sta/NetworkClass.hh"
45 
46 namespace sta {
47 class dbSta;
48 class BfsFwdIterator;
49 class dbNetwork;
50 class LibertyPort;
51 }  // namespace sta
52 
53 namespace odb {
54 class dbDatabase;
55 class dbBTerm;
56 }  // namespace odb
57 
58 namespace utl {
59 class Logger;
60 }
61 
62 namespace mpl {
63 
64 class Layout;
65 
66 using std::map;
67 using std::pair;
68 using std::set;
69 using std::string;
70 using std::unordered_map;
71 using std::vector;
72 
73 typedef set<Macro*> MacroSet;
74 // vertex -> fanin macro set
75 typedef map<sta::Vertex*, MacroSet> VertexFaninMap;
76 typedef pair<Macro*, Macro*> MacroPair;
77 // from/to -> weight
78 // weight = from/pin -> to/pin count
79 typedef map<MacroPair, int> AdjWeightMap;
80 
81 enum class CoreEdge
82 {
83   West,
84   East,
85   North,
86   South,
87 };
88 
89 constexpr int core_edge_count = 4;
90 const char* coreEdgeString(CoreEdge edge);
91 CoreEdge coreEdgeFromIndex(int edge_index);
92 int coreEdgeIndex(CoreEdge edge);
93 
94 class Macro
95 {
96  public:
97   Macro(double _lx, double _ly, double _w, double _h, odb::dbInst* _dbInstPtr);
98   Macro(double _lx, double _ly, const Macro& copy_from);
99   string name();
100 
101   double lx, ly;
102   double w, h;
103   odb::dbInst* dbInstPtr;
104 };
105 
106 class MacroSpacings
107 {
108  public:
109   MacroSpacings();
110   MacroSpacings(double halo_x,
111                 double halo_y,
112                 double channel_x,
113                 double channel_y);
114   void setHalo(double halo_x, double halo_y);
115   void setChannel(double channel_x, double channel_y);
116   void setChannelX(double channel_x);
117   void setChannelY(double channel_y);
getHaloX()118   double getHaloX() const { return halo_x_; }
getHaloY()119   double getHaloY() const { return halo_y_; }
getChannelX()120   double getChannelX() const { return channel_x_; }
getChannelY()121   double getChannelY() const { return channel_y_; }
122   double getSpacingX() const;
123   double getSpacingY() const;
124 
125  private:
126   double halo_x_, halo_y_, channel_x_, channel_y_;
127 };
128 
129 class MacroPlacer
130 {
131  public:
132   MacroPlacer();
133   void init(odb::dbDatabase* db, sta::dbSta* sta, utl::Logger* log);
134   void setDebug(bool partitions);
135 
136   void setHalo(double halo_x, double halo_y);
137   void setChannel(double channel_x, double channel_y);
138   void setVerboseLevel(int verbose);
139   void setFenceRegion(double lx, double ly, double ux, double uy);
140   void setSnapLayer(odb::dbTechLayer* snap_layer);
141 
142   void placeMacrosCornerMinWL();
143   void placeMacrosCornerMaxWl();
144   int getSolutionCount();
145 
146   // return weighted wire-length to get best solution
147   double getWeightedWL();
148   int weight(int idx11, int idx12);
149   int macroIndex(odb::dbInst* inst);
150   MacroSpacings& getSpacings(const Macro& macro);
151   double paddedWidth(const Macro& macro);
152   double paddedHeight(const Macro& macro);
153 
macro(int idx)154   Macro& macro(int idx) { return macros_[idx]; }
macroCount()155   size_t macroCount() { return macros_.size(); }
156 
157  private:
158   void findMacros();
159   bool isMissingLiberty();
160 
161   void init();
162   // Update Macro Location from Partition info
163   void updateMacroLocations(Partition& part);
164   void updateDbInstLocations();
165   void updateMacroPartMap(Partition& part, MacroPartMap& macroPartMap);
166   vector<pair<Partition, Partition>> getPartitions(const Layout& layout,
167                                                    const Partition& partition,
168                                                    bool isHorizontal);
169   void cutRoundUp(const Layout& layout, double& cutLine, bool isHorizontal);
170   void setDbInstLocations(Partition& partition);
171 
172   // graph based adjacencies
173   void findAdjacencies();
174   void seedFaninBfs(sta::BfsFwdIterator& bfs, VertexFaninMap& vertex_fanins);
175   void findFanins(sta::BfsFwdIterator& bfs, VertexFaninMap& vertex_fanins);
176   void copyFaninsAcrossRegisters(sta::BfsFwdIterator& bfs,
177                                  VertexFaninMap& vertex_fanins);
178   void findAdjWeights(VertexFaninMap& vertex_fanins, AdjWeightMap& adj_map);
179   sta::Pin* findSeqOutPin(sta::Instance* inst, sta::LibertyPort* out_port);
180   void fillMacroWeights(AdjWeightMap& adj_map);
181   CoreEdge findNearestEdge(odb::dbBTerm* bTerm);
182   string faninName(Macro* macro);
183   int macroIndex(Macro* macro);
184   bool macroIndexIsEdge(Macro* macro);
185   string macroIndexName(int index);
186 
187   void reportEdgePinCounts();
188 
189   ////////////////////////////////////////////////////////////////
190 
191   odb::dbDatabase* db_;
192   sta::dbSta* sta_;
193   utl::Logger* logger_;
194   odb::dbTechLayer* snap_layer_;
195 
196   bool connection_driven_;
197 
198   // macro idx/idx pair -> give each
199   vector<vector<int>> macro_weights_;
200   // macro Information
201   vector<Macro> macros_;
202   // dbInst* --> macros_'s index
203   unordered_map<odb::dbInst*, int> macro_inst_map_;
204 
205   MacroSpacings default_macro_spacings_;
206   unordered_map<odb::dbInst*, MacroSpacings> macro_spacings_;
207 
208   double lx_, ly_, ux_, uy_;
209   int verbose_;
210   int solution_count_;
211 
212   bool gui_debug_;
213   bool gui_debug_partitions_;
214   // Number of register levels to look through for macro adjacency.
215   static constexpr int reg_adjacency_depth_ = 3;
216 };
217 
218 class Layout
219 {
220  public:
221   Layout();
222   Layout(double lx, double ly, double ux, double uy);
223   Layout(Layout& orig, Partition& part);
224 
lx()225   double lx() const { return lx_; }
ly()226   double ly() const { return ly_; }
ux()227   double ux() const { return ux_; }
uy()228   double uy() const { return uy_; }
229 
230   void setLx(double lx);
231   void setLy(double ly);
232   void setUx(double ux);
233   void setUy(double uy);
234 
235  private:
236   double lx_, ly_, ux_, uy_;
237 };
238 
239 }  // namespace mpl
240