courgette/adjustment_method.cc

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