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