| OLD | NEW |
| 1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "courgette/adjustment_method.h" | 5 #include "courgette/adjustment_method.h" |
| 6 | 6 |
| 7 #include <algorithm> | 7 #include <algorithm> |
| 8 #include <list> | 8 #include <list> |
| 9 #include <map> | 9 #include <map> |
| 10 #include <set> | 10 #include <set> |
| 11 #include <string> | 11 #include <string> |
| 12 #include <vector> | 12 #include <vector> |
| 13 | 13 |
| 14 #include "base/basictypes.h" | 14 #include "base/basictypes.h" |
| 15 #include "base/logging.h" | 15 #include "base/logging.h" |
| 16 #include "base/string_number_conversions.h" | 16 #include "base/string_number_conversions.h" |
| 17 #include "base/string_util.h" | 17 #include "base/string_util.h" |
| 18 | 18 |
| 19 #include "courgette/assembly_program.h" | 19 #include "courgette/assembly_program.h" |
| 20 #include "courgette/courgette.h" | 20 #include "courgette/courgette.h" |
| 21 #include "courgette/encoded_program.h" | 21 #include "courgette/encoded_program.h" |
| 22 #include "courgette/image_info.h" | 22 #include "courgette/image_info.h" |
| 23 | 23 |
| 24 namespace courgette { | 24 namespace courgette { |
| 25 | 25 |
| 26 // We have three discretionary information logging levels for algorithm | |
| 27 // development. For now just configure with #defines. | |
| 28 // TODO(sra): make dependent of some configurable setting. | |
| 29 #define NO_LOG DLOG_IF(INFO, false) | |
| 30 // #define ALOG1 LOG(INFO) | |
| 31 // #define ALOG2 LOG(INFO) | |
| 32 // #define ALOG3 LOG(INFO) | |
| 33 #define ALOG1 NO_LOG | |
| 34 #define ALOG2 NO_LOG | |
| 35 #define ALOG3 NO_LOG | |
| 36 | |
| 37 //////////////////////////////////////////////////////////////////////////////// | 26 //////////////////////////////////////////////////////////////////////////////// |
| 38 | 27 |
| 39 class NullAdjustmentMethod : public AdjustmentMethod { | 28 class NullAdjustmentMethod : public AdjustmentMethod { |
| 40 bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) { | 29 bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) { |
| 41 return true; | 30 return true; |
| 42 } | 31 } |
| 43 }; | 32 }; |
| 44 | 33 |
| 45 //////////////////////////////////////////////////////////////////////////////// | 34 //////////////////////////////////////////////////////////////////////////////// |
| 46 | 35 |
| (...skipping 188 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 235 p_root_ = MakeRootNode(p_trace_); | 224 p_root_ = MakeRootNode(p_trace_); |
| 236 AddToQueue(p_root_); | 225 AddToQueue(p_root_); |
| 237 | 226 |
| 238 while (!worklist_.empty()) { | 227 while (!worklist_.empty()) { |
| 239 Node* node = *worklist_.begin(); | 228 Node* node = *worklist_.begin(); |
| 240 node->in_queue_ = false; | 229 node->in_queue_ = false; |
| 241 worklist_.erase(node); | 230 worklist_.erase(node); |
| 242 TrySolveNode(node); | 231 TrySolveNode(node); |
| 243 } | 232 } |
| 244 | 233 |
| 245 ALOG1 << unsolved_.size() << " unsolved items"; | 234 VLOG(2) << unsolved_.size() << " unsolved items"; |
| 246 return true; | 235 return true; |
| 247 } | 236 } |
| 248 | 237 |
| 249 private: | 238 private: |
| 250 void AddToQueue(Node* node) { | 239 void AddToQueue(Node* node) { |
| 251 if (node->length_ >= 10) { | 240 if (node->length_ >= 10) { |
| 252 ALOG3 << "Length clipped " << ToString(node->prev_); | 241 VLOG(4) << "Length clipped " << ToString(node->prev_); |
| 253 return; | 242 return; |
| 254 } | 243 } |
| 255 if (node->in_queue_) { | 244 if (node->in_queue_) { |
| 256 LOG(ERROR) << "Double add " << ToString(node); | 245 LOG(ERROR) << "Double add " << ToString(node); |
| 257 return; | 246 return; |
| 258 } | 247 } |
| 259 // just to be sure data for prioritizing is available | 248 // just to be sure data for prioritizing is available |
| 260 ExtendNode(node, p_trace_); | 249 ExtendNode(node, p_trace_); |
| 261 // SkipCommittedLabels(node); | 250 // SkipCommittedLabels(node); |
| 262 if (node->edges_in_frequency_order.empty()) | 251 if (node->edges_in_frequency_order.empty()) |
| 263 return; | 252 return; |
| 264 node->in_queue_ = true; | 253 node->in_queue_ = true; |
| 265 worklist_.insert(node); | 254 worklist_.insert(node); |
| 266 } | 255 } |
| 267 | 256 |
| 268 void SkipCommittedLabels(Node* node) { | 257 void SkipCommittedLabels(Node* node) { |
| 269 ExtendNode(node, p_trace_); | 258 ExtendNode(node, p_trace_); |
| 270 uint32 skipped = 0; | 259 uint32 skipped = 0; |
| 271 while (!node->edges_in_frequency_order.empty() && | 260 while (!node->edges_in_frequency_order.empty() && |
| 272 node->edges_in_frequency_order.front()->in_edge_->assignment_) { | 261 node->edges_in_frequency_order.front()->in_edge_->assignment_) { |
| 273 ++skipped; | 262 ++skipped; |
| 274 node->edges_in_frequency_order.pop_front(); | 263 node->edges_in_frequency_order.pop_front(); |
| 275 } | 264 } |
| 276 if (skipped > 0) | 265 if (skipped > 0) |
| 277 ALOG3 << "Skipped " << skipped << " at " << ToString(node); | 266 VLOG(4) << "Skipped " << skipped << " at " << ToString(node); |
| 278 } | 267 } |
| 279 | 268 |
| 280 void TrySolveNode(Node* p_node) { | 269 void TrySolveNode(Node* p_node) { |
| 281 Node* front = p_node->edges_in_frequency_order.front(); | 270 Node* front = p_node->edges_in_frequency_order.front(); |
| 282 if (front->in_edge_->assignment_) { | 271 if (front->in_edge_->assignment_) { |
| 283 p_node->edges_in_frequency_order.pop_front(); | 272 p_node->edges_in_frequency_order.pop_front(); |
| 284 AddToQueue(front); | 273 AddToQueue(front); |
| 285 AddToQueue(p_node); | 274 AddToQueue(p_node); |
| 286 return; | 275 return; |
| 287 } | 276 } |
| 288 | 277 |
| 289 // Compare frequencies of unassigned edges, and either make | 278 // Compare frequencies of unassigned edges, and either make |
| 290 // assignment(s) or move node to unsolved list | 279 // assignment(s) or move node to unsolved list |
| 291 | 280 |
| 292 Node* m_node = FindModelNode(p_node); | 281 Node* m_node = FindModelNode(p_node); |
| 293 | 282 |
| 294 if (m_node == NULL) { | 283 if (m_node == NULL) { |
| 295 ALOG1 << "Can't find model node"; | 284 VLOG(2) << "Can't find model node"; |
| 296 unsolved_.insert(p_node); | 285 unsolved_.insert(p_node); |
| 297 return; | 286 return; |
| 298 } | 287 } |
| 299 ExtendNode(m_node, m_trace_); | 288 ExtendNode(m_node, m_trace_); |
| 300 | 289 |
| 301 // Lets just try greedy | 290 // Lets just try greedy |
| 302 | 291 |
| 303 SkipCommittedLabels(m_node); | 292 SkipCommittedLabels(m_node); |
| 304 if (m_node->edges_in_frequency_order.empty()) { | 293 if (m_node->edges_in_frequency_order.empty()) { |
| 305 ALOG3 << "Punting, no elements left in model vs " | 294 VLOG(4) << "Punting, no elements left in model vs " |
| 306 << p_node->edges_in_frequency_order.size(); | 295 << p_node->edges_in_frequency_order.size(); |
| 307 unsolved_.insert(p_node); | 296 unsolved_.insert(p_node); |
| 308 return; | 297 return; |
| 309 } | 298 } |
| 310 Node* m_match = m_node->edges_in_frequency_order.front(); | 299 Node* m_match = m_node->edges_in_frequency_order.front(); |
| 311 Node* p_match = p_node->edges_in_frequency_order.front(); | 300 Node* p_match = p_node->edges_in_frequency_order.front(); |
| 312 | 301 |
| 313 if (p_match->count_ > 1.1 * m_match->count_ || | 302 if (p_match->count_ > 1.1 * m_match->count_ || |
| 314 m_match->count_ > 1.1 * p_match->count_) { | 303 m_match->count_ > 1.1 * p_match->count_) { |
| 315 ALOG2 << "Tricky distribution " | 304 VLOG(3) << "Tricky distribution " |
| 316 << p_match->count_ << ":" << m_match->count_ << " " | 305 << p_match->count_ << ":" << m_match->count_ << " " |
| 317 << ToString(p_match) << " vs " << ToString(m_match); | 306 << ToString(p_match) << " vs " << ToString(m_match); |
| 318 return; | 307 return; |
| 319 } | 308 } |
| 320 | 309 |
| 321 m_node->edges_in_frequency_order.pop_front(); | 310 m_node->edges_in_frequency_order.pop_front(); |
| 322 p_node->edges_in_frequency_order.pop_front(); | 311 p_node->edges_in_frequency_order.pop_front(); |
| 323 | 312 |
| 324 LabelInfo* p_label_info = p_match->in_edge_; | 313 LabelInfo* p_label_info = p_match->in_edge_; |
| 325 LabelInfo* m_label_info = m_match->in_edge_; | 314 LabelInfo* m_label_info = m_match->in_edge_; |
| 326 int m_index = p_label_info->label_->index_; | 315 int m_index = p_label_info->label_->index_; |
| 327 if (m_index != Label::kNoIndex) { | 316 if (m_index != Label::kNoIndex) { |
| 328 ALOG1 << "Cant use unassigned label from model " << m_index; | 317 VLOG(2) << "Cant use unassigned label from model " << m_index; |
| 329 unsolved_.insert(p_node); | 318 unsolved_.insert(p_node); |
| 330 return; | 319 return; |
| 331 } | 320 } |
| 332 | 321 |
| 333 Assign(p_label_info, m_label_info); | 322 Assign(p_label_info, m_label_info); |
| 334 | 323 |
| 335 AddToQueue(p_match); // find matches within new match | 324 AddToQueue(p_match); // find matches within new match |
| 336 AddToQueue(p_node); // and more matches within this node | 325 AddToQueue(p_node); // and more matches within this node |
| 337 } | 326 } |
| 338 | 327 |
| 339 void Assign(LabelInfo* p_info, LabelInfo* m_info) { | 328 void Assign(LabelInfo* p_info, LabelInfo* m_info) { |
| 340 AssignOne(p_info, m_info); | 329 AssignOne(p_info, m_info); |
| 341 ALOG3 << "Assign " << ToString(p_info) << " := " << ToString(m_info); | 330 VLOG(4) << "Assign " << ToString(p_info) << " := " << ToString(m_info); |
| 342 // Now consider unassigned adjacent addresses | 331 // Now consider unassigned adjacent addresses |
| 343 TryExtendAssignment(p_info, m_info); | 332 TryExtendAssignment(p_info, m_info); |
| 344 } | 333 } |
| 345 | 334 |
| 346 void AssignOne(LabelInfo* p_info, LabelInfo* m_info) { | 335 void AssignOne(LabelInfo* p_info, LabelInfo* m_info) { |
| 347 p_info->label_->index_ = m_info->label_->index_; | 336 p_info->label_->index_ = m_info->label_->index_; |
| 348 | 337 |
| 349 // Mark as assigned | 338 // Mark as assigned |
| 350 m_info->assignment_ = p_info; | 339 m_info->assignment_ = p_info; |
| 351 p_info->assignment_ = m_info; | 340 p_info->assignment_ = m_info; |
| (...skipping 27 matching lines...) Expand all Loading... |
| 379 break; | 368 break; |
| 380 } | 369 } |
| 381 } | 370 } |
| 382 | 371 |
| 383 // The label has inconsistent numbers of references, it is probably not | 372 // The label has inconsistent numbers of references, it is probably not |
| 384 // the same thing. | 373 // the same thing. |
| 385 if (m_info_next->refs_ != p_info_next->refs_) { | 374 if (m_info_next->refs_ != p_info_next->refs_) { |
| 386 break; | 375 break; |
| 387 } | 376 } |
| 388 | 377 |
| 389 ALOG3 << " Extending assignment -> " | 378 VLOG(4) << " Extending assignment -> " |
| 390 << ToString(p_info_next) << " := " << ToString(m_info_next); | 379 << ToString(p_info_next) << " := " << ToString(m_info_next); |
| 391 | 380 |
| 392 AssignOne(p_info_next, m_info_next); | 381 AssignOne(p_info_next, m_info_next); |
| 393 | 382 |
| 394 if (p_info_next->refs_ == m_info_next->refs_ && | 383 if (p_info_next->refs_ == m_info_next->refs_ && |
| 395 p_info_next->refs_ == 1) { | 384 p_info_next->refs_ == 1) { |
| 396 TryExtendSequence(p_info_next->positions_[0], | 385 TryExtendSequence(p_info_next->positions_[0], |
| 397 m_info_next->positions_[0]); | 386 m_info_next->positions_[0]); |
| 398 TryExtendSequenceBackwards(p_info_next->positions_[0], | 387 TryExtendSequenceBackwards(p_info_next->positions_[0], |
| 399 m_info_next->positions_[0]); | 388 m_info_next->positions_[0]); |
| 400 } | 389 } |
| (...skipping 18 matching lines...) Expand all Loading... |
| 419 LabelInfo* m_info_prev_prev = m_info_prev->prev_addr_; | 408 LabelInfo* m_info_prev_prev = m_info_prev->prev_addr_; |
| 420 LabelInfo* p_info_prev_prev = p_info_prev->prev_addr_; | 409 LabelInfo* p_info_prev_prev = p_info_prev->prev_addr_; |
| 421 | 410 |
| 422 // The the label has inconsistent numbers of references, it is | 411 // The the label has inconsistent numbers of references, it is |
| 423 // probably not the same thing | 412 // probably not the same thing |
| 424 if (m_info_prev->refs_ != p_info_prev->refs_) { | 413 if (m_info_prev->refs_ != p_info_prev->refs_) { |
| 425 break; | 414 break; |
| 426 } | 415 } |
| 427 | 416 |
| 428 AssignOne(p_info_prev, m_info_prev); | 417 AssignOne(p_info_prev, m_info_prev); |
| 429 ALOG3 << " Extending assignment <- " << ToString(p_info_prev) << " := " | 418 VLOG(4) << " Extending assignment <- " << ToString(p_info_prev) << " := " |
| 430 << ToString(m_info_prev); | 419 << ToString(m_info_prev); |
| 431 | 420 |
| 432 p_info_prev = p_info_prev_prev; | 421 p_info_prev = p_info_prev_prev; |
| 433 m_info_prev = m_info_prev_prev; | 422 m_info_prev = m_info_prev_prev; |
| 434 } | 423 } |
| 435 } | 424 } |
| 436 | 425 |
| 437 uint32 TryExtendSequence(uint32 p_pos_start, uint32 m_pos_start) { | 426 uint32 TryExtendSequence(uint32 p_pos_start, uint32 m_pos_start) { |
| 438 uint32 p_pos = p_pos_start + 1; | 427 uint32 p_pos = p_pos_start + 1; |
| 439 uint32 m_pos = m_pos_start + 1; | 428 uint32 m_pos = m_pos_start + 1; |
| 440 | 429 |
| (...skipping 11 matching lines...) Expand all Loading... |
| 452 break; | 441 break; |
| 453 ++p_pos; | 442 ++p_pos; |
| 454 ++m_pos; | 443 ++m_pos; |
| 455 continue; | 444 continue; |
| 456 } | 445 } |
| 457 | 446 |
| 458 if (p_info->refs_ != m_info->refs_) | 447 if (p_info->refs_ != m_info->refs_) |
| 459 break; | 448 break; |
| 460 | 449 |
| 461 AssignOne(p_info, m_info); | 450 AssignOne(p_info, m_info); |
| 462 ALOG3 << " Extending assignment seq" | 451 VLOG(4) << " Extending assignment seq[+" << p_pos - p_pos_start |
| 463 << "[+" << p_pos - p_pos_start << "]" | 452 << "] -> " << ToString(p_info) << " := " << ToString(m_info); |
| 464 << " -> " | |
| 465 << ToString(p_info) << " := " << ToString(m_info); | |
| 466 | 453 |
| 467 ++p_pos; | 454 ++p_pos; |
| 468 ++m_pos; | 455 ++m_pos; |
| 469 } | 456 } |
| 470 | 457 |
| 471 return p_pos - p_pos_start; | 458 return p_pos - p_pos_start; |
| 472 } | 459 } |
| 473 | 460 |
| 474 uint32 TryExtendSequenceBackwards(uint32 p_pos_start, uint32 m_pos_start) { | 461 uint32 TryExtendSequenceBackwards(uint32 p_pos_start, uint32 m_pos_start) { |
| 475 if (p_pos_start == 0 || m_pos_start == 0) | 462 if (p_pos_start == 0 || m_pos_start == 0) |
| (...skipping 14 matching lines...) Expand all Loading... |
| 490 break; | 477 break; |
| 491 --p_pos; | 478 --p_pos; |
| 492 --m_pos; | 479 --m_pos; |
| 493 continue; | 480 continue; |
| 494 } | 481 } |
| 495 | 482 |
| 496 if (p_info->refs_ != m_info->refs_) | 483 if (p_info->refs_ != m_info->refs_) |
| 497 break; | 484 break; |
| 498 | 485 |
| 499 AssignOne(p_info, m_info); | 486 AssignOne(p_info, m_info); |
| 500 ALOG3 << " Extending assignment seq" | 487 VLOG(4) << " Extending assignment seq[-" << p_pos_start - p_pos |
| 501 << "[-" << p_pos_start - p_pos << "]" | 488 << "] <- " << ToString(p_info) << " := " << ToString(m_info); |
| 502 << " <- " | |
| 503 << ToString(p_info) << " := " << ToString(m_info); | |
| 504 | 489 |
| 505 --p_pos; | 490 --p_pos; |
| 506 --m_pos; | 491 --m_pos; |
| 507 } | 492 } |
| 508 | 493 |
| 509 return p_pos - p_pos_start; | 494 return p_pos - p_pos_start; |
| 510 } | 495 } |
| 511 | 496 |
| 512 Node* FindModelNode(Node* node) { | 497 Node* FindModelNode(Node* node) { |
| 513 if (node->prev_ == NULL) | 498 if (node->prev_ == NULL) |
| 514 return m_root_; | 499 return m_root_; |
| 515 | 500 |
| 516 Node* m_parent = FindModelNode(node->prev_); | 501 Node* m_parent = FindModelNode(node->prev_); |
| 517 if (m_parent == NULL) { | 502 if (m_parent == NULL) { |
| 518 return NULL; | 503 return NULL; |
| 519 } | 504 } |
| 520 | 505 |
| 521 ExtendNode(m_parent, m_trace_); | 506 ExtendNode(m_parent, m_trace_); |
| 522 | 507 |
| 523 LabelInfo* p_label = node->in_edge_; | 508 LabelInfo* p_label = node->in_edge_; |
| 524 LabelInfo* m_label = p_label->assignment_; | 509 LabelInfo* m_label = p_label->assignment_; |
| 525 if (m_label == NULL) { | 510 if (m_label == NULL) { |
| 526 ALOG1 << "Expected assigned prefix"; | 511 VLOG(2) << "Expected assigned prefix"; |
| 527 return NULL; | 512 return NULL; |
| 528 } | 513 } |
| 529 | 514 |
| 530 Node::Edges::iterator e = m_parent->edges_.find(m_label); | 515 Node::Edges::iterator e = m_parent->edges_.find(m_label); |
| 531 if (e == m_parent->edges_.end()) { | 516 if (e == m_parent->edges_.end()) { |
| 532 ALOG2 << "Expected defined edge in parent"; | 517 VLOG(3) << "Expected defined edge in parent"; |
| 533 return NULL; | 518 return NULL; |
| 534 } | 519 } |
| 535 | 520 |
| 536 return e->second; | 521 return e->second; |
| 537 } | 522 } |
| 538 | 523 |
| 539 Node* MakeRootNode(const Trace& trace) { | 524 Node* MakeRootNode(const Trace& trace) { |
| 540 Node* node = new Node(NULL, NULL); | 525 Node* node = new Node(NULL, NULL); |
| 541 all_nodes_.push_back(node); | 526 all_nodes_.push_back(node); |
| 542 for (size_t i = 0; i < trace.size(); ++i) { | 527 for (size_t i = 0; i < trace.size(); ++i) { |
| (...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 582 | 567 |
| 583 class GraphAdjuster : public AdjustmentMethod { | 568 class GraphAdjuster : public AdjustmentMethod { |
| 584 public: | 569 public: |
| 585 GraphAdjuster() | 570 GraphAdjuster() |
| 586 : prog_(NULL), | 571 : prog_(NULL), |
| 587 model_(NULL), | 572 model_(NULL), |
| 588 debug_label_index_gen_(0) {} | 573 debug_label_index_gen_(0) {} |
| 589 ~GraphAdjuster() {} | 574 ~GraphAdjuster() {} |
| 590 | 575 |
| 591 bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) { | 576 bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) { |
| 592 LOG(INFO) << "GraphAdjuster::Adjust"; | 577 VLOG(1) << "GraphAdjuster::Adjust"; |
| 593 prog_ = program; | 578 prog_ = program; |
| 594 model_ = &model; | 579 model_ = &model; |
| 595 debug_label_index_gen_ = 0; | 580 debug_label_index_gen_ = 0; |
| 596 return Finish(); | 581 return Finish(); |
| 597 } | 582 } |
| 598 | 583 |
| 599 bool Finish() { | 584 bool Finish() { |
| 600 prog_->UnassignIndexes(); | 585 prog_->UnassignIndexes(); |
| 601 CollectTraces(model_, &model_abs32_, &model_rel32_, true); | 586 CollectTraces(model_, &model_abs32_, &model_rel32_, true); |
| 602 CollectTraces(prog_, &prog_abs32_, &prog_rel32_, false); | 587 CollectTraces(prog_, &prog_abs32_, &prog_rel32_, false); |
| (...skipping 97 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 700 AdjustmentMethod* method = AdjustmentMethod::MakeProductionAdjustmentMethod(); | 685 AdjustmentMethod* method = AdjustmentMethod::MakeProductionAdjustmentMethod(); |
| 701 bool ok = method->Adjust(model, program); | 686 bool ok = method->Adjust(model, program); |
| 702 method->Destroy(); | 687 method->Destroy(); |
| 703 if (ok) | 688 if (ok) |
| 704 return C_OK; | 689 return C_OK; |
| 705 else | 690 else |
| 706 return C_ADJUSTMENT_FAILED; | 691 return C_ADJUSTMENT_FAILED; |
| 707 } | 692 } |
| 708 | 693 |
| 709 } // namespace courgette | 694 } // namespace courgette |
| OLD | NEW |