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 <stddef.h>
   8 #include <stdint.h>
   9
  10 #include <algorithm>
  11 #include <list>
  12 #include <map>
  13 #include <set>
  14 #include <string>
  15 #include <vector>
  16
  17 #include "base/logging.h"
  18 #include "base/macros.h"
  19 #include "base/strings/string_number_conversions.h"
  20 #include "base/strings/stringprintf.h"
  21 #include "courgette/assembly_program.h"
  22 #include "courgette/courgette.h"
  23 #include "courgette/encoded_program.h"
  24
  25 namespace courgette {
  26
  27 ////////////////////////////////////////////////////////////////////////////////
  28
  29 class NullAdjustmentMethod : public AdjustmentMethod {
  30   bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) {
  31     return true;
  32   }
  33 };
  34
  35 ////////////////////////////////////////////////////////////////////////////////
  36
  37 // The purpose of adjustment is to assign indexes to Labels of a program 'p' to
  38 // make the sequence of indexes similar to a 'model' program 'm'.  Labels
  39 // themselves don't have enough information to do this job, so we work with a
  40 // LabelInfo surrogate for each label.
  41 //
  42 class LabelInfo {
  43  public:
  44   Label* label_;              // The label that this info a surrogate for.
  45
  46   // Information used only in debugging messages.
  47   uint32_t is_model_ : 1;      // Is the label in the model?
  48   uint32_t debug_index_ : 31;  // An unique small number for naming the label.
  49
  50   uint32_t refs_;  // Number of times this Label is referenced.
  51
  52   LabelInfo* assignment_;     // Label from other program corresponding to this.
  53
  54   // LabelInfos are in a doubly linked list ordered by address (label_->rva_) so
  55   // we can quickly find Labels adjacent in address order.
  56   LabelInfo* next_addr_;      // Label(Info) at next highest address.
  57   LabelInfo* prev_addr_;      // Label(Info) at next lowest address.
  58
  59   std::vector<uint32_t> positions_;  // Offsets into the trace of references.
  60
  61   // Just a no-argument constructor and copy constructor.  Actual LabelInfo
  62   // objects are allocated in std::pair structs in a std::map.
  63   LabelInfo()
  64       : label_(nullptr),
  65         is_model_(false),
  66         debug_index_(0),
  67         refs_(0),
  68         assignment_(nullptr),
  69         next_addr_(nullptr),
  70         prev_addr_(nullptr) {}
  71
  72  private:
  73   void operator=(const LabelInfo*);  // Disallow assignment only.
  74
  75   // Public compiler generated copy constructor is needed to constuct
  76   // std::pair<Label*, LabelInfo> so that fresh LabelInfos can be allocated
  77   // inside a std::map.
  78 };
  79
  80 struct OrderLabelInfoByAddressAscending {
  81   bool operator()(const LabelInfo* a, const LabelInfo* b) const {
  82     return a->label_->rva_ < b->label_->rva_;
  83   }
  84 };
  85
  86 static std::string ToString(LabelInfo* info) {
  87   std::string s;
  88   base::StringAppendF(&s, "%c%d", "pm"[info->is_model_], info->debug_index_);
  89   if (info->label_->index_ != Label::kNoIndex)
  90     base::StringAppendF(&s, " (%d)", info->label_->index_);
  91
  92   base::StringAppendF(&s, " #%u", info->refs_);
  93   return s;
  94 }
  95
  96 // General graph matching is exponential, essentially trying all permutations.
  97 // The exponential algorithm can be made faster by avoiding consideration of
  98 // impossible or unlikely matches.  We can make the matching practical by eager
  99 // matching - by looking for likely matches and commiting to them, and using the
 100 // committed assignment as the basis for further matching.
 101 //
 102 // The basic eager graph-matching assignment is based on several ideas:
 103 //
 104 //  * The strongest match will be for parts of the program that have not
 105 //    changed.  If part of a program has not changed, then the number of
 106 //    references to a label will be the same, and corresponding pairs of
 107 //    adjacent labels will have the same RVA difference.
 108 //
 109 //  * Some assignments are 'obvious' if you look at the distribution.  Example:
 110 //    if both the program and the model have a label that is referred to much
 111 //    more often than the next most refered-to label, it is likely the two
 112 //    labels correspond.
 113 //
 114 //  * If a label from the program corresponds to a label in the model, it is
 115 //    likely that the labels near the corresponding labels also match.  A
 116 //    conservative way of extending the match is to assign only those labels
 117 //    which have exactly the same address offset and reference count.
 118 //
 119 //  * If two labels correspond, then we can try to match up the references
 120 //    before and after the labels in the reference stream.  For this to be
 121 //    practical, the number of references has to be small, e.g. each label has
 122 //    exactly one reference.
 123 //
 124
 125 // Note: we also tried a completely different approach: random assignment
 126 // followed by simulated annealing.  This produced similar results.  The results
 127 // were not as good for very small differences because the simulated annealing
 128 // never quite hit the groove.  And simulated annealing was several orders of
 129 // magnitude slower.
 130
 131
 132 // TRIE node for suffix strings in the label reference sequence.
 133 //
 134 // We dynamically build a trie for both the program and model, growing the trie
 135 // as necessary.  The trie node for a (possibly) empty string of label
 136 // references contains the distribution of labels following the string.  The
 137 // roots node (for the empty string) thus contains the simple distribution of
 138 // labels within the label reference stream.
 139
 140 struct Node {
 141   Node(LabelInfo* in_edge, Node* prev)
 142       : in_edge_(in_edge), prev_(prev), count_(0),
 143         in_queue_(false) {
 144     length_ = 1 + (prev_ ? prev_->length_ : 0);
 145   }
 146   LabelInfo* in_edge_;  //
 147   Node* prev_;          // Node at shorter length.
 148   int count_;           // Frequency of this path in Trie.
 149   int length_;
 150   typedef std::map<LabelInfo*, Node*> Edges;
 151   Edges edges_;
 152   std::vector<int> places_;   // Indexes into sequence of this item.
 153   std::list<Node*> edges_in_frequency_order;
 154
 155   bool in_queue_;
 156   bool Extended() const { return !edges_.empty(); }
 157
 158   uint32_t Weight() const { return edges_in_frequency_order.front()->count_; }
 159 };
 160
 161 static std::string ToString(Node* node) {
 162   std::vector<std::string> prefix;
 163   for (Node* n = node;  n->prev_;  n = n->prev_)
 164     prefix.push_back(ToString(n->in_edge_));
 165
 166   std::string s;
 167   s += "{";
 168   const char* sep = "";
 169   while (!prefix.empty()) {
 170     s += sep;
 171     sep = ",";
 172     s += prefix.back();
 173     prefix.pop_back();
 174   }
 175
 176   s += base::StringPrintf("%u", node->count_);
 177   s += " @";
 178   s += base::NumberToString(node->edges_in_frequency_order.size());
 179   s += "}";
 180   return s;
 181 }
 182
 183 typedef std::vector<LabelInfo*> Trace;
 184
 185 struct OrderNodeByCountDecreasing {
 186   bool operator()(Node* a, Node* b) const {
 187     if (a->count_ != b->count_)
 188       return  (a->count_) > (b->count_);
 189     return a->places_.at(0) < b->places_.at(0);  // Prefer first occuring.
 190   }
 191 };
 192
 193 struct OrderNodeByWeightDecreasing {
 194   bool operator()(Node* a, Node* b) const {
 195     // (Maybe tie-break on total count, followed by lowest assigned node indexes
 196     // in path.)
 197     uint32_t a_weight = a->Weight();
 198     uint32_t b_weight = b->Weight();
 199     if (a_weight != b_weight)
 200       return a_weight > b_weight;
 201     if (a->length_ != b->length_)
 202       return a->length_ > b->length_;            // Prefer longer.
 203     return a->places_.at(0) < b->places_.at(0);  // Prefer first occuring.
 204   }
 205 };
 206
 207 typedef std::set<Node*, OrderNodeByWeightDecreasing> NodeQueue;
 208
 209 class AssignmentProblem {
 210  public:
 211   AssignmentProblem(const Trace& model, const Trace& problem)
 212       : m_trace_(model),
 213         p_trace_(problem),
 214         m_root_(nullptr),
 215         p_root_(nullptr) {}
 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_t 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 == nullptr) {
 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_t TryExtendSequence(uint32_t p_pos_start, uint32_t m_pos_start) {
 427     uint32_t p_pos = p_pos_start + 1;
 428     uint32_t 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_ == nullptr) != (m_info->assignment_ == nullptr))
 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_t TryExtendSequenceBackwards(uint32_t p_pos_start,
 462                                       uint32_t m_pos_start) {
 463     if (p_pos_start == 0  ||  m_pos_start == 0)
 464       return 0;
 465
 466     uint32_t p_pos = p_pos_start - 1;
 467     uint32_t m_pos = m_pos_start - 1;
 468
 469     while (p_pos > 0  &&  m_pos > 0) {
 470       LabelInfo* p_info = p_trace_[p_pos];
 471       LabelInfo* m_info = m_trace_[m_pos];
 472
 473       if ((p_info->assignment_ == nullptr) != (m_info->assignment_ == nullptr))
 474         break;
 475
 476       if (p_info->assignment_ && m_info->assignment_) {
 477         if (p_info->label_->index_ != m_info->label_->index_)
 478           break;
 479         --p_pos;
 480         --m_pos;
 481         continue;
 482       }
 483
 484       if (p_info->refs_ != m_info->refs_)
 485         break;
 486
 487       AssignOne(p_info, m_info);
 488       VLOG(4) << "    Extending assignment seq[-" << p_pos_start - p_pos
 489               << "] <- " << ToString(p_info) << " := " << ToString(m_info);
 490
 491       --p_pos;
 492       --m_pos;
 493     }
 494
 495     return p_pos - p_pos_start;
 496   }
 497
 498   Node* FindModelNode(Node* node) {
 499     if (node->prev_ == nullptr)
 500       return m_root_;
 501
 502     Node* m_parent = FindModelNode(node->prev_);
 503     if (m_parent == nullptr) {
 504       return nullptr;
 505     }
 506
 507     ExtendNode(m_parent, m_trace_);
 508
 509     LabelInfo* p_label = node->in_edge_;
 510     LabelInfo* m_label = p_label->assignment_;
 511     if (m_label == nullptr) {
 512       VLOG(2) << "Expected assigned prefix";
 513       return nullptr;
 514     }
 515
 516     Node::Edges::iterator e = m_parent->edges_.find(m_label);
 517     if (e == m_parent->edges_.end()) {
 518       VLOG(3) << "Expected defined edge in parent";
 519       return nullptr;
 520     }
 521
 522     return e->second;
 523   }
 524
 525   Node* MakeRootNode(const Trace& trace) {
 526     Node* node = new Node(nullptr, nullptr);
 527     all_nodes_.push_back(node);
 528     for (uint32_t i = 0; i < trace.size(); ++i) {
 529       ++node->count_;
 530       node->places_.push_back(i);
 531     }
 532     return node;
 533   }
 534
 535   void ExtendNode(Node* node, const Trace& trace) {
 536     // Make sure trie is filled in at this node.
 537     if (node->Extended())
 538       return;
 539     for (size_t i = 0; i < node->places_.size();  ++i) {
 540       uint32_t index = node->places_.at(i);
 541       if (index < trace.size()) {
 542         LabelInfo* item = trace.at(index);
 543         Node*& slot = node->edges_[item];
 544         if (slot == nullptr) {
 545           slot = new Node(item, node);
 546           all_nodes_.push_back(slot);
 547           node->edges_in_frequency_order.push_back(slot);
 548         }
 549         slot->places_.push_back(index + 1);
 550         ++slot->count_;
 551       }
 552     }
 553     node->edges_in_frequency_order.sort(OrderNodeByCountDecreasing());
 554   }
 555
 556   const Trace& m_trace_;
 557   const Trace& p_trace_;
 558   Node* m_root_;
 559   Node* p_root_;
 560
 561   NodeQueue worklist_;
 562   NodeQueue unsolved_;
 563
 564   std::vector<Node*> all_nodes_;
 565
 566   DISALLOW_COPY_AND_ASSIGN(AssignmentProblem);
 567 };
 568
 569 class GraphAdjuster : public AdjustmentMethod {
 570  public:
 571   GraphAdjuster()
 572       : prog_(nullptr), model_(nullptr), debug_label_index_gen_(0) {}
 573   ~GraphAdjuster() = default;
 574
 575   bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) {
 576     VLOG(1) << "GraphAdjuster::Adjust";
 577     prog_ = program;
 578     model_ = &model;
 579     debug_label_index_gen_ = 0;
 580     return Finish();
 581   }
 582
 583   bool Finish() {
 584     prog_->UnassignIndexes();
 585     CollectTraces(model_, &model_abs32_, &model_rel32_, true);
 586     CollectTraces(prog_,  &prog_abs32_,  &prog_rel32_,  false);
 587     Solve(model_abs32_, prog_abs32_);
 588     Solve(model_rel32_, prog_rel32_);
 589     prog_->AssignRemainingIndexes();
 590     return true;
 591   }
 592
 593  private:
 594   void CollectTraces(const AssemblyProgram* program, Trace* abs32, Trace* rel32,
 595                      bool is_model) {
 596     for (Label* label : program->abs32_label_annotations())
 597       ReferenceLabel(abs32, is_model, label);
 598     for (Label* label : program->rel32_label_annotations())
 599       ReferenceLabel(rel32, is_model, label);
 600
 601     // TODO(sra): we could simply append all the labels in index order to
 602     // incorporate some costing for entropy (bigger deltas) that will be
 603     // introduced into the label address table by non-monotonic ordering.  This
 604     // would have some knock-on effects to parts of the algorithm that work on
 605     // single-occurrence labels.
 606   }
 607
 608   void Solve(const Trace& model, const Trace& problem) {
 609     LinkLabelInfos(model);
 610     LinkLabelInfos(problem);
 611     AssignmentProblem a(model, problem);
 612     a.Solve();
 613   }
 614
 615   void LinkLabelInfos(const Trace& trace) {
 616     typedef std::set<LabelInfo*, OrderLabelInfoByAddressAscending> Ordered;
 617     Ordered ordered;
 618     for (Trace::const_iterator p = trace.begin();  p != trace.end();  ++p)
 619       ordered.insert(*p);
 620     LabelInfo* prev = nullptr;
 621     for (Ordered::iterator p = ordered.begin();  p != ordered.end();  ++p) {
 622       LabelInfo* curr = *p;
 623       if (prev) prev->next_addr_ = curr;
 624       curr->prev_addr_ = prev;
 625       prev = curr;
 626
 627       if (curr->positions_.size() != curr->refs_)
 628         NOTREACHED();
 629     }
 630   }
 631
 632   void ReferenceLabel(Trace* trace, bool is_model, Label* label) {
 633     trace->push_back(
 634         MakeLabelInfo(label, is_model, static_cast<uint32_t>(trace->size())));
 635   }
 636
 637   LabelInfo* MakeLabelInfo(Label* label, bool is_model, uint32_t position) {
 638     LabelInfo& slot = label_infos_[label];
 639     if (slot.label_ == nullptr) {
 640       slot.label_ = label;
 641       slot.is_model_ = is_model;
 642       slot.debug_index_ = ++debug_label_index_gen_;
 643     }
 644     slot.positions_.push_back(position);
 645     ++slot.refs_;
 646     return &slot;
 647   }
 648
 649   AssemblyProgram* prog_;         // Program to be adjusted, owned by caller.
 650   const AssemblyProgram* model_;  // Program to be mimicked, owned by caller.
 651
 652   Trace model_abs32_;
 653   Trace model_rel32_;
 654   Trace prog_abs32_;
 655   Trace prog_rel32_;
 656
 657   int debug_label_index_gen_;
 658
 659   // Note LabelInfo is allocated inside map, so the LabelInfo lifetimes are
 660   // managed by the map.
 661   std::map<Label*, LabelInfo> label_infos_;
 662
 663  private:
 664   DISALLOW_COPY_AND_ASSIGN(GraphAdjuster);
 665 };
 666
 667
 668 ////////////////////////////////////////////////////////////////////////////////
 669
 670 void AdjustmentMethod::Destroy() { delete this; }
 671
 672 AdjustmentMethod* AdjustmentMethod::MakeNullAdjustmentMethod() {
 673   return new NullAdjustmentMethod();
 674 }
 675
 676 AdjustmentMethod* AdjustmentMethod::MakeTrieAdjustmentMethod() {
 677   return new GraphAdjuster();
 678 }
 679
 680 Status Adjust(const AssemblyProgram& model, AssemblyProgram* program) {
 681   AdjustmentMethod* method = AdjustmentMethod::MakeProductionAdjustmentMethod();
 682   bool ok = method->Adjust(model, program);
 683   method->Destroy();
 684   if (ok)
 685     return C_OK;
 686   else
 687     return C_ADJUSTMENT_FAILED;
 688 }
 689
 690 }  // namespace courgette