adjustment_method.cc 21 KB

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