Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(435)

Side by Side Diff: courgette/adjustment_method.cc

Issue 3904002: Convert LOG(INFO) to VLOG(1) - courgette/. (Closed) Base URL: svn://chrome-svn/chrome/trunk/src/
Patch Set: Created 10 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « no previous file | courgette/adjustment_method_2.cc » ('j') | courgette/encoded_program.cc » ('J')
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
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
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
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
OLDNEW
« no previous file with comments | « no previous file | courgette/adjustment_method_2.cc » ('j') | courgette/encoded_program.cc » ('J')

Powered by Google App Engine
This is Rietveld 408576698