[go: nahoru, domu]
Google Git
Sign in
chromium / chromium / src / 2fb496132bb949cce6c8824e388a6f0ec5137e39 / . / courgette / adjustment_method.cc
blob: 8217b38e94503d8b555794c6229ebd9740827c7f [file] [log] [blame]
Avi Drissman0ff8a7e2022-09-13 18:35:42[diff] [blame]1// Copyright 2011 The Chromium Authors
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "courgette/adjustment_method.h"
6
aviab98dcc92015-12-21 19:35:33[diff] [blame]7#include <stddef.h>
8#include <stdint.h>
9
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]10#include <algorithm>
11#include <list>
12#include <map>
13#include <set>
14#include <string>
15#include <vector>
16
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]17#include "base/logging.h"
Keishi Hattori0e45c022021-11-27 09:25:52[diff] [blame]18#include "base/memory/raw_ptr.h"
Ali Hijazi55179192022-11-09 16:28:51[diff] [blame]19#include "base/memory/raw_ref.h"
avi@chromium.org68c986e2013-06-11 13:26:25[diff] [blame]20#include "base/strings/string_number_conversions.h"
21#include "base/strings/stringprintf.h"
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]22#include "courgette/assembly_program.h"
23#include "courgette/courgette.h"
24#include "courgette/encoded_program.h"
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]25
26namespace courgette {
27
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]28////////////////////////////////////////////////////////////////////////////////
29
30class NullAdjustmentMethod : public AdjustmentMethod {
31 bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) {
32 return true;
33 }
34};
35
36////////////////////////////////////////////////////////////////////////////////
37
38// The purpose of adjustment is to assign indexes to Labels of a program 'p' to
39// make the sequence of indexes similar to a 'model' program 'm'. Labels
40// themselves don't have enough information to do this job, so we work with a
41// LabelInfo surrogate for each label.
42//
43class LabelInfo {
44 public:
Keishi Hattori0e45c022021-11-27 09:25:52[diff] [blame]45 raw_ptr<Label> label_; // The label that this info a surrogate for.
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]46
47 // Information used only in debugging messages.
aviab98dcc92015-12-21 19:35:33[diff] [blame]48 uint32_t is_model_ : 1; // Is the label in the model?
49 uint32_t debug_index_ : 31; // An unique small number for naming the label.
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]50
aviab98dcc92015-12-21 19:35:33[diff] [blame]51 uint32_t refs_; // Number of times this Label is referenced.
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]52
Keishi Hattori0e45c022021-11-27 09:25:52[diff] [blame]53 raw_ptr<LabelInfo>
54 assignment_; // Label from other program corresponding to this.
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]55
56 // LabelInfos are in a doubly linked list ordered by address (label_->rva_) so
57 // we can quickly find Labels adjacent in address order.
Keishi Hattori0e45c022021-11-27 09:25:52[diff] [blame]58 raw_ptr<LabelInfo> next_addr_; // Label(Info) at next highest address.
59 raw_ptr<LabelInfo> prev_addr_; // Label(Info) at next lowest address.
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]60
aviab98dcc92015-12-21 19:35:33[diff] [blame]61 std::vector<uint32_t> positions_; // Offsets into the trace of references.
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]62
63 // Just a no-argument constructor and copy constructor. Actual LabelInfo
64 // objects are allocated in std::pair structs in a std::map.
65 LabelInfo()
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]66 : label_(nullptr),
67 is_model_(false),
68 debug_index_(0),
69 refs_(0),
70 assignment_(nullptr),
71 next_addr_(nullptr),
72 prev_addr_(nullptr) {}
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]73
74 private:
75 void operator=(const LabelInfo*); // Disallow assignment only.
76
77 // Public compiler generated copy constructor is needed to constuct
78 // std::pair<Label*, LabelInfo> so that fresh LabelInfos can be allocated
79 // inside a std::map.
80};
81
82struct OrderLabelInfoByAddressAscending {
83 bool operator()(const LabelInfo* a, const LabelInfo* b) const {
84 return a->label_->rva_ < b->label_->rva_;
85 }
86};
87
88static std::string ToString(LabelInfo* info) {
89 std::string s;
tfarina@chromium.orga77fa2dc2010-11-15 12:11:11[diff] [blame]90 base::StringAppendF(&s, "%c%d", "pm"[info->is_model_], info->debug_index_);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]91 if (info->label_->index_ != Label::kNoIndex)
tfarina@chromium.orga77fa2dc2010-11-15 12:11:11[diff] [blame]92 base::StringAppendF(&s, " (%d)", info->label_->index_);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]93
tfarina@chromium.orga77fa2dc2010-11-15 12:11:11[diff] [blame]94 base::StringAppendF(&s, " #%u", info->refs_);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]95 return s;
96}
97
98// General graph matching is exponential, essentially trying all permutations.
99// The exponential algorithm can be made faster by avoiding consideration of
100// impossible or unlikely matches. We can make the matching practical by eager
101// matching - by looking for likely matches and commiting to them, and using the
102// committed assignment as the basis for further matching.
103//
104// The basic eager graph-matching assignment is based on several ideas:
105//
106// * The strongest match will be for parts of the program that have not
107// changed. If part of a program has not changed, then the number of
108// references to a label will be the same, and corresponding pairs of
109// adjacent labels will have the same RVA difference.
110//
111// * Some assignments are 'obvious' if you look at the distribution. Example:
112// if both the program and the model have a label that is referred to much
113// more often than the next most refered-to label, it is likely the two
114// labels correspond.
115//
116// * If a label from the program corresponds to a label in the model, it is
117// likely that the labels near the corresponding labels also match. A
118// conservative way of extending the match is to assign only those labels
119// which have exactly the same address offset and reference count.
120//
121// * If two labels correspond, then we can try to match up the references
122// before and after the labels in the reference stream. For this to be
123// practical, the number of references has to be small, e.g. each label has
124// exactly one reference.
125//
126
127// Note: we also tried a completely different approach: random assignment
128// followed by simulated annealing. This produced similar results. The results
129// were not as good for very small differences because the simulated annealing
130// never quite hit the groove. And simulated annealing was several orders of
131// magnitude slower.
132
133
134// TRIE node for suffix strings in the label reference sequence.
135//
136// We dynamically build a trie for both the program and model, growing the trie
137// as necessary. The trie node for a (possibly) empty string of label
138// references contains the distribution of labels following the string. The
139// roots node (for the empty string) thus contains the simple distribution of
140// labels within the label reference stream.
141
142struct Node {
143 Node(LabelInfo* in_edge, Node* prev)
144 : in_edge_(in_edge), prev_(prev), count_(0),
145 in_queue_(false) {
146 length_ = 1 + (prev_ ? prev_->length_ : 0);
147 }
Keishi Hattori0e45c022021-11-27 09:25:52[diff] [blame]148 raw_ptr<LabelInfo> in_edge_; //
149 raw_ptr<Node> prev_; // Node at shorter length.
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]150 int count_; // Frequency of this path in Trie.
151 int length_;
152 typedef std::map<LabelInfo*, Node*> Edges;
153 Edges edges_;
154 std::vector<int> places_; // Indexes into sequence of this item.
155 std::list<Node*> edges_in_frequency_order;
156
157 bool in_queue_;
erg@google.com6775e40a2011-03-04 21:03:47[diff] [blame]158 bool Extended() const { return !edges_.empty(); }
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]159
aviab98dcc92015-12-21 19:35:33[diff] [blame]160 uint32_t Weight() const { return edges_in_frequency_order.front()->count_; }
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]161};
162
163static std::string ToString(Node* node) {
164 std::vector<std::string> prefix;
165 for (Node* n = node; n->prev_; n = n->prev_)
166 prefix.push_back(ToString(n->in_edge_));
167
168 std::string s;
169 s += "{";
170 const char* sep = "";
171 while (!prefix.empty()) {
172 s += sep;
173 sep = ",";
174 s += prefix.back();
175 prefix.pop_back();
176 }
177
groby@chromium.org7d3cbc92013-03-18 22:33:04[diff] [blame]178 s += base::StringPrintf("%u", node->count_);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]179 s += " @";
Daniel Cheng3d199b12017-12-12 03:51:09[diff] [blame]180 s += base::NumberToString(node->edges_in_frequency_order.size());
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]181 s += "}";
182 return s;
183}
184
Ali Hijazie63cbaf62023-12-20 19:29:35[diff] [blame]185typedef std::vector<raw_ptr<LabelInfo, VectorExperimental>> Trace;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]186
187struct OrderNodeByCountDecreasing {
188 bool operator()(Node* a, Node* b) const {
189 if (a->count_ != b->count_)
190 return (a->count_) > (b->count_);
191 return a->places_.at(0) < b->places_.at(0); // Prefer first occuring.
192 }
193};
194
195struct OrderNodeByWeightDecreasing {
196 bool operator()(Node* a, Node* b) const {
197 // (Maybe tie-break on total count, followed by lowest assigned node indexes
198 // in path.)
aviab98dcc92015-12-21 19:35:33[diff] [blame]199 uint32_t a_weight = a->Weight();
200 uint32_t b_weight = b->Weight();
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]201 if (a_weight != b_weight)
202 return a_weight > b_weight;
203 if (a->length_ != b->length_)
204 return a->length_ > b->length_; // Prefer longer.
205 return a->places_.at(0) < b->places_.at(0); // Prefer first occuring.
206 }
207};
208
Ali Hijazi133b2d92024-02-09 14:01:52[diff] [blame]209typedef std::set<raw_ptr<Node, SetExperimental>, OrderNodeByWeightDecreasing>
210 NodeQueue;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]211
212class AssignmentProblem {
213 public:
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]214 AssignmentProblem(const Trace& model, const Trace& problem)
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]215 : m_trace_(model),
sra@chromium.orgd38c3a22009-07-22 01:30:06[diff] [blame]216 p_trace_(problem),
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]217 m_root_(nullptr),
218 p_root_(nullptr) {}
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]219
Peter Boströmc68c5aa2021-09-28 00:28:00[diff] [blame]220 AssignmentProblem(const AssignmentProblem&) = delete;
221 AssignmentProblem& operator=(const AssignmentProblem&) = delete;
222
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]223 ~AssignmentProblem() {
224 for (size_t i = 0; i < all_nodes_.size(); ++i)
225 delete all_nodes_[i];
226 }
227
228 bool Solve() {
Ali Hijazi55179192022-11-09 16:28:51[diff] [blame]229 m_root_ = MakeRootNode(*m_trace_);
230 p_root_ = MakeRootNode(*p_trace_);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]231 AddToQueue(p_root_);
232
233 while (!worklist_.empty()) {
234 Node* node = *worklist_.begin();
235 node->in_queue_ = false;
236 worklist_.erase(node);
237 TrySolveNode(node);
238 }
239
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]240 VLOG(2) << unsolved_.size() << " unsolved items";
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]241 return true;
242 }
243
244 private:
245 void AddToQueue(Node* node) {
246 if (node->length_ >= 10) {
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]247 VLOG(4) << "Length clipped " << ToString(node->prev_);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]248 return;
249 }
250 if (node->in_queue_) {
251 LOG(ERROR) << "Double add " << ToString(node);
252 return;
253 }
254 // just to be sure data for prioritizing is available
Ali Hijazi55179192022-11-09 16:28:51[diff] [blame]255 ExtendNode(node, *p_trace_);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]256 // SkipCommittedLabels(node);
257 if (node->edges_in_frequency_order.empty())
258 return;
259 node->in_queue_ = true;
260 worklist_.insert(node);
261 }
262
263 void SkipCommittedLabels(Node* node) {
Ali Hijazi55179192022-11-09 16:28:51[diff] [blame]264 ExtendNode(node, *p_trace_);
aviab98dcc92015-12-21 19:35:33[diff] [blame]265 uint32_t skipped = 0;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]266 while (!node->edges_in_frequency_order.empty() &&
267 node->edges_in_frequency_order.front()->in_edge_->assignment_) {
268 ++skipped;
269 node->edges_in_frequency_order.pop_front();
270 }
271 if (skipped > 0)
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]272 VLOG(4) << "Skipped " << skipped << " at " << ToString(node);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]273 }
274
275 void TrySolveNode(Node* p_node) {
276 Node* front = p_node->edges_in_frequency_order.front();
277 if (front->in_edge_->assignment_) {
278 p_node->edges_in_frequency_order.pop_front();
279 AddToQueue(front);
280 AddToQueue(p_node);
281 return;
282 }
283
284 // Compare frequencies of unassigned edges, and either make
285 // assignment(s) or move node to unsolved list
286
287 Node* m_node = FindModelNode(p_node);
288
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]289 if (m_node == nullptr) {
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]290 VLOG(2) << "Can't find model node";
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]291 unsolved_.insert(p_node);
292 return;
293 }
Ali Hijazi55179192022-11-09 16:28:51[diff] [blame]294 ExtendNode(m_node, *m_trace_);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]295
296 // Lets just try greedy
297
298 SkipCommittedLabels(m_node);
299 if (m_node->edges_in_frequency_order.empty()) {
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]300 VLOG(4) << "Punting, no elements left in model vs "
301 << p_node->edges_in_frequency_order.size();
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]302 unsolved_.insert(p_node);
303 return;
304 }
305 Node* m_match = m_node->edges_in_frequency_order.front();
306 Node* p_match = p_node->edges_in_frequency_order.front();
307
308 if (p_match->count_ > 1.1 * m_match->count_ ||
309 m_match->count_ > 1.1 * p_match->count_) {
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]310 VLOG(3) << "Tricky distribution "
311 << p_match->count_ << ":" << m_match->count_ << " "
312 << ToString(p_match) << " vs " << ToString(m_match);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]313 return;
314 }
315
316 m_node->edges_in_frequency_order.pop_front();
317 p_node->edges_in_frequency_order.pop_front();
318
319 LabelInfo* p_label_info = p_match->in_edge_;
320 LabelInfo* m_label_info = m_match->in_edge_;
321 int m_index = p_label_info->label_->index_;
322 if (m_index != Label::kNoIndex) {
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]323 VLOG(2) << "Cant use unassigned label from model " << m_index;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]324 unsolved_.insert(p_node);
325 return;
326 }
327
328 Assign(p_label_info, m_label_info);
329
330 AddToQueue(p_match); // find matches within new match
331 AddToQueue(p_node); // and more matches within this node
332 }
333
334 void Assign(LabelInfo* p_info, LabelInfo* m_info) {
335 AssignOne(p_info, m_info);
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]336 VLOG(4) << "Assign " << ToString(p_info) << " := " << ToString(m_info);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]337 // Now consider unassigned adjacent addresses
338 TryExtendAssignment(p_info, m_info);
339 }
340
341 void AssignOne(LabelInfo* p_info, LabelInfo* m_info) {
342 p_info->label_->index_ = m_info->label_->index_;
343
344 // Mark as assigned
345 m_info->assignment_ = p_info;
346 p_info->assignment_ = m_info;
347 }
348
349 void TryExtendAssignment(LabelInfo* p_info, LabelInfo* m_info) {
350 RVA m_rva_base = m_info->label_->rva_;
351 RVA p_rva_base = p_info->label_->rva_;
352
353 LabelInfo* m_info_next = m_info->next_addr_;
354 LabelInfo* p_info_next = p_info->next_addr_;
355 for ( ; m_info_next && p_info_next; ) {
356 if (m_info_next->assignment_)
357 break;
358
359 RVA m_rva = m_info_next->label_->rva_;
360 RVA p_rva = p_info_next->label_->rva_;
361
362 if (m_rva - m_rva_base != p_rva - p_rva_base) {
363 // previous label was pointing to something that is different size
364 break;
365 }
366 LabelInfo* m_info_next_next = m_info_next->next_addr_;
367 LabelInfo* p_info_next_next = p_info_next->next_addr_;
368 if (m_info_next_next && p_info_next_next) {
369 RVA m_rva_next = m_info_next_next->label_->rva_;
370 RVA p_rva_next = p_info_next_next->label_->rva_;
371 if (m_rva_next - m_rva != p_rva_next - p_rva) {
372 // Since following labels are no longer in address lockstep, assume
373 // this address has a difference.
374 break;
375 }
376 }
377
378 // The label has inconsistent numbers of references, it is probably not
379 // the same thing.
380 if (m_info_next->refs_ != p_info_next->refs_) {
381 break;
382 }
383
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]384 VLOG(4) << " Extending assignment -> "
385 << ToString(p_info_next) << " := " << ToString(m_info_next);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]386
387 AssignOne(p_info_next, m_info_next);
388
389 if (p_info_next->refs_ == m_info_next->refs_ &&
390 p_info_next->refs_ == 1) {
391 TryExtendSequence(p_info_next->positions_[0],
392 m_info_next->positions_[0]);
393 TryExtendSequenceBackwards(p_info_next->positions_[0],
394 m_info_next->positions_[0]);
395 }
396
397 p_info_next = p_info_next_next;
398 m_info_next = m_info_next_next;
399 }
400
401 LabelInfo* m_info_prev = m_info->prev_addr_;
402 LabelInfo* p_info_prev = p_info->prev_addr_;
403 for ( ; m_info_prev && p_info_prev; ) {
404 if (m_info_prev->assignment_)
405 break;
406
407 RVA m_rva = m_info_prev->label_->rva_;
408 RVA p_rva = p_info_prev->label_->rva_;
409
410 if (m_rva - m_rva_base != p_rva - p_rva_base) {
411 // previous label was pointing to something that is different size
412 break;
413 }
414 LabelInfo* m_info_prev_prev = m_info_prev->prev_addr_;
415 LabelInfo* p_info_prev_prev = p_info_prev->prev_addr_;
416
417 // The the label has inconsistent numbers of references, it is
418 // probably not the same thing
419 if (m_info_prev->refs_ != p_info_prev->refs_) {
420 break;
421 }
422
423 AssignOne(p_info_prev, m_info_prev);
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]424 VLOG(4) << " Extending assignment <- " << ToString(p_info_prev) << " := "
425 << ToString(m_info_prev);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]426
427 p_info_prev = p_info_prev_prev;
428 m_info_prev = m_info_prev_prev;
429 }
430 }
431
aviab98dcc92015-12-21 19:35:33[diff] [blame]432 uint32_t TryExtendSequence(uint32_t p_pos_start, uint32_t m_pos_start) {
433 uint32_t p_pos = p_pos_start + 1;
434 uint32_t m_pos = m_pos_start + 1;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]435
Ali Hijazi55179192022-11-09 16:28:51[diff] [blame]436 while (p_pos < p_trace_->size() && m_pos < m_trace_->size()) {
437 LabelInfo* p_info = (*p_trace_)[p_pos];
438 LabelInfo* m_info = (*m_trace_)[m_pos];
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]439
440 // To match, either (1) both are assigned or (2) both are unassigned.
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]441 if ((p_info->assignment_ == nullptr) != (m_info->assignment_ == nullptr))
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]442 break;
443
444 // If they are assigned, it needs to be consistent (same index).
445 if (p_info->assignment_ && m_info->assignment_) {
446 if (p_info->label_->index_ != m_info->label_->index_)
447 break;
448 ++p_pos;
449 ++m_pos;
450 continue;
451 }
452
453 if (p_info->refs_ != m_info->refs_)
454 break;
455
456 AssignOne(p_info, m_info);
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]457 VLOG(4) << " Extending assignment seq[+" << p_pos - p_pos_start
458 << "] -> " << ToString(p_info) << " := " << ToString(m_info);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]459
460 ++p_pos;
461 ++m_pos;
462 }
463
464 return p_pos - p_pos_start;
465 }
466
aviab98dcc92015-12-21 19:35:33[diff] [blame]467 uint32_t TryExtendSequenceBackwards(uint32_t p_pos_start,
468 uint32_t m_pos_start) {
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]469 if (p_pos_start == 0 || m_pos_start == 0)
470 return 0;
471
aviab98dcc92015-12-21 19:35:33[diff] [blame]472 uint32_t p_pos = p_pos_start - 1;
473 uint32_t m_pos = m_pos_start - 1;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]474
475 while (p_pos > 0 && m_pos > 0) {
Ali Hijazi55179192022-11-09 16:28:51[diff] [blame]476 LabelInfo* p_info = (*p_trace_)[p_pos];
477 LabelInfo* m_info = (*m_trace_)[m_pos];
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]478
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]479 if ((p_info->assignment_ == nullptr) != (m_info->assignment_ == nullptr))
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]480 break;
481
482 if (p_info->assignment_ && m_info->assignment_) {
483 if (p_info->label_->index_ != m_info->label_->index_)
484 break;
485 --p_pos;
486 --m_pos;
487 continue;
488 }
489
490 if (p_info->refs_ != m_info->refs_)
491 break;
492
493 AssignOne(p_info, m_info);
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]494 VLOG(4) << " Extending assignment seq[-" << p_pos_start - p_pos
495 << "] <- " << ToString(p_info) << " := " << ToString(m_info);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]496
497 --p_pos;
498 --m_pos;
499 }
500
501 return p_pos - p_pos_start;
502 }
503
504 Node* FindModelNode(Node* node) {
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]505 if (node->prev_ == nullptr)
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]506 return m_root_;
507
508 Node* m_parent = FindModelNode(node->prev_);
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]509 if (m_parent == nullptr) {
510 return nullptr;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]511 }
512
Ali Hijazi55179192022-11-09 16:28:51[diff] [blame]513 ExtendNode(m_parent, *m_trace_);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]514
515 LabelInfo* p_label = node->in_edge_;
516 LabelInfo* m_label = p_label->assignment_;
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]517 if (m_label == nullptr) {
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]518 VLOG(2) << "Expected assigned prefix";
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]519 return nullptr;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]520 }
521
522 Node::Edges::iterator e = m_parent->edges_.find(m_label);
523 if (e == m_parent->edges_.end()) {
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]524 VLOG(3) << "Expected defined edge in parent";
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]525 return nullptr;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]526 }
527
528 return e->second;
529 }
530
531 Node* MakeRootNode(const Trace& trace) {
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]532 Node* node = new Node(nullptr, nullptr);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]533 all_nodes_.push_back(node);
aviab98dcc92015-12-21 19:35:33[diff] [blame]534 for (uint32_t i = 0; i < trace.size(); ++i) {
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]535 ++node->count_;
536 node->places_.push_back(i);
537 }
538 return node;
539 }
540
541 void ExtendNode(Node* node, const Trace& trace) {
542 // Make sure trie is filled in at this node.
543 if (node->Extended())
544 return;
545 for (size_t i = 0; i < node->places_.size(); ++i) {
aviab98dcc92015-12-21 19:35:33[diff] [blame]546 uint32_t index = node->places_.at(i);
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]547 if (index < trace.size()) {
548 LabelInfo* item = trace.at(index);
549 Node*& slot = node->edges_[item];
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]550 if (slot == nullptr) {
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]551 slot = new Node(item, node);
552 all_nodes_.push_back(slot);
553 node->edges_in_frequency_order.push_back(slot);
554 }
555 slot->places_.push_back(index + 1);
556 ++slot->count_;
557 }
558 }
559 node->edges_in_frequency_order.sort(OrderNodeByCountDecreasing());
560 }
561
Ali Hijazi55179192022-11-09 16:28:51[diff] [blame]562 const raw_ref<const Trace> m_trace_;
563 const raw_ref<const Trace> p_trace_;
Keishi Hattori0e45c022021-11-27 09:25:52[diff] [blame]564 raw_ptr<Node> m_root_;
565 raw_ptr<Node> p_root_;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]566
567 NodeQueue worklist_;
568 NodeQueue unsolved_;
569
Ali Hijazie63cbaf62023-12-20 19:29:35[diff] [blame]570 std::vector<raw_ptr<Node, VectorExperimental>> all_nodes_;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]571};
572
573class GraphAdjuster : public AdjustmentMethod {
574 public:
sra@chromium.orgd38c3a22009-07-22 01:30:06[diff] [blame]575 GraphAdjuster()
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]576 : prog_(nullptr), model_(nullptr), debug_label_index_gen_(0) {}
Peter Boströmc68c5aa2021-09-28 00:28:00[diff] [blame]577
578 GraphAdjuster(const GraphAdjuster&) = delete;
579 GraphAdjuster& operator=(const GraphAdjuster&) = delete;
580
Chris Watkins2903a822017-11-30 03:19:57[diff] [blame]581 ~GraphAdjuster() = default;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]582
583 bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) {
pkasting@chromium.org18cca202010-10-21 20:40:58[diff] [blame]584 VLOG(1) << "GraphAdjuster::Adjust";
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]585 prog_ = program;
586 model_ = &model;
587 debug_label_index_gen_ = 0;
588 return Finish();
589 }
590
591 bool Finish() {
592 prog_->UnassignIndexes();
593 CollectTraces(model_, &model_abs32_, &model_rel32_, true);
594 CollectTraces(prog_, &prog_abs32_, &prog_rel32_, false);
595 Solve(model_abs32_, prog_abs32_);
596 Solve(model_rel32_, prog_rel32_);
597 prog_->AssignRemainingIndexes();
598 return true;
599 }
600
601 private:
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]602 void CollectTraces(const AssemblyProgram* program, Trace* abs32, Trace* rel32,
603 bool is_model) {
huangsc4155eb2017-04-13 20:47:07[diff] [blame]604 for (Label* label : program->abs32_label_annotations())
605 ReferenceLabel(abs32, is_model, label);
606 for (Label* label : program->rel32_label_annotations())
607 ReferenceLabel(rel32, is_model, label);
huangs99a5a8c2016-10-28 22:29:31[diff] [blame]608
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]609 // TODO(sra): we could simply append all the labels in index order to
610 // incorporate some costing for entropy (bigger deltas) that will be
611 // introduced into the label address table by non-monotonic ordering. This
612 // would have some knock-on effects to parts of the algorithm that work on
tommi@chromium.org43a9e242011-04-06 17:42:45[diff] [blame]613 // single-occurrence labels.
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]614 }
615
616 void Solve(const Trace& model, const Trace& problem) {
617 LinkLabelInfos(model);
618 LinkLabelInfos(problem);
619 AssignmentProblem a(model, problem);
620 a.Solve();
621 }
622
623 void LinkLabelInfos(const Trace& trace) {
624 typedef std::set<LabelInfo*, OrderLabelInfoByAddressAscending> Ordered;
625 Ordered ordered;
626 for (Trace::const_iterator p = trace.begin(); p != trace.end(); ++p)
627 ordered.insert(*p);
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]628 LabelInfo* prev = nullptr;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]629 for (Ordered::iterator p = ordered.begin(); p != ordered.end(); ++p) {
630 LabelInfo* curr = *p;
631 if (prev) prev->next_addr_ = curr;
632 curr->prev_addr_ = prev;
633 prev = curr;
634
635 if (curr->positions_.size() != curr->refs_)
636 NOTREACHED();
637 }
638 }
639
huangs99a5a8c2016-10-28 22:29:31[diff] [blame]640 void ReferenceLabel(Trace* trace, bool is_model, Label* label) {
aviab98dcc92015-12-21 19:35:33[diff] [blame]641 trace->push_back(
642 MakeLabelInfo(label, is_model, static_cast<uint32_t>(trace->size())));
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]643 }
644
aviab98dcc92015-12-21 19:35:33[diff] [blame]645 LabelInfo* MakeLabelInfo(Label* label, bool is_model, uint32_t position) {
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]646 LabelInfo& slot = label_infos_[label];
Raul Tambre5bd92982019-03-28 06:21:55[diff] [blame]647 if (slot.label_ == nullptr) {
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]648 slot.label_ = label;
649 slot.is_model_ = is_model;
650 slot.debug_index_ = ++debug_label_index_gen_;
651 }
652 slot.positions_.push_back(position);
653 ++slot.refs_;
654 return &slot;
655 }
656
Keishi Hattori0e45c022021-11-27 09:25:52[diff] [blame]657 raw_ptr<AssemblyProgram> prog_; // Program to be adjusted, owned by caller.
658 raw_ptr<const AssemblyProgram>
659 model_; // Program to be mimicked, owned by caller.
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]660
661 Trace model_abs32_;
662 Trace model_rel32_;
663 Trace prog_abs32_;
664 Trace prog_rel32_;
665
666 int debug_label_index_gen_;
667
668 // Note LabelInfo is allocated inside map, so the LabelInfo lifetimes are
669 // managed by the map.
670 std::map<Label*, LabelInfo> label_infos_;
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]671};
672
673
674////////////////////////////////////////////////////////////////////////////////
675
676void AdjustmentMethod::Destroy() { delete this; }
677
678AdjustmentMethod* AdjustmentMethod::MakeNullAdjustmentMethod() {
679 return new NullAdjustmentMethod();
680}
681
sra@chromium.org8cd96962009-06-03 23:28:14[diff] [blame]682AdjustmentMethod* AdjustmentMethod::MakeTrieAdjustmentMethod() {
sra@chromium.org04ca1bc2009-05-08 23:00:29[diff] [blame]683 return new GraphAdjuster();
684}
685
686Status Adjust(const AssemblyProgram& model, AssemblyProgram* program) {
687 AdjustmentMethod* method = AdjustmentMethod::MakeProductionAdjustmentMethod();
688 bool ok = method->Adjust(model, program);
689 method->Destroy();
690 if (ok)
691 return C_OK;
692 else
693 return C_ADJUSTMENT_FAILED;
694}
695
696} // namespace courgette