1//===-- DifferenceEngine.cpp - Structural function/module comparison ------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This header defines the implementation of the LLVM difference
11// engine, which structurally compares global values within a module.
12//
13//===----------------------------------------------------------------------===//
14
15#include "DifferenceEngine.h"
16
17#include "llvm/Constants.h"
18#include "llvm/Function.h"
19#include "llvm/Instructions.h"
20#include "llvm/Module.h"
21#include "llvm/ADT/DenseMap.h"
22#include "llvm/ADT/DenseSet.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/ADT/StringRef.h"
25#include "llvm/ADT/StringSet.h"

--- 236 unchanged lines hidden (view full) ---

262 if (Complain) Engine.log("different predicates");
263 return true;
264 }
265 } else if (isa<CallInst>(L)) {
266 return diffCallSites(CallSite(L), CallSite(R), Complain);
267 } else if (isa<PHINode>(L)) {
268 // FIXME: implement.
269
270 // This is really weird; type uniquing is broken?
271 if (L->getType() != R->getType()) {
272 if (!L->getType()->isPointerTy() || !R->getType()->isPointerTy()) {
273 if (Complain) Engine.log("different phi types");
274 return true;
275 }
276 }
277 return false;
278

--- 223 unchanged lines hidden (view full) ---

502 const unsigned MatchCost = 0;
503
504 assert(TentativeValues.empty());
505
506 // Initialize the first column.
507 for (unsigned I = 0; I != NL+1; ++I) {
508 Cur[I].Cost = I * LeftCost;
509 for (unsigned J = 0; J != I; ++J)
510 Cur[I].Path.push_back(DC_left);
511 }
512
513 for (BasicBlock::iterator RI = RStart; RI != RE; ++RI) {
514 // Initialize the first row.
515 Next[0] = Cur[0];
516 Next[0].Cost += RightCost;
517 Next[0].Path.push_back(DC_right);
518
519 unsigned Index = 1;
520 for (BasicBlock::iterator LI = LStart; LI != LE; ++LI, ++Index) {
521 if (matchForBlockDiff(&*LI, &*RI)) {
522 Next[Index] = Cur[Index-1];
523 Next[Index].Cost += MatchCost;
524 Next[Index].Path.push_back(DC_match);
525 TentativeValues.insert(std::make_pair(&*LI, &*RI));
526 } else if (Next[Index-1].Cost <= Cur[Index].Cost) {
527 Next[Index] = Next[Index-1];
528 Next[Index].Cost += LeftCost;
529 Next[Index].Path.push_back(DC_left);
530 } else {
531 Next[Index] = Cur[Index];
532 Next[Index].Cost += RightCost;
533 Next[Index].Path.push_back(DC_right);
534 }
535 }
536
537 std::swap(Cur, Next);
538 }
539
540 // We don't need the tentative values anymore; everything from here
541 // on out should be non-tentative.
542 TentativeValues.clear();
543
544 SmallVectorImpl<char> &Path = Cur[NL].Path;
545 BasicBlock::iterator LI = LStart, RI = RStart;
546
547 DiffLogBuilder Diff(Engine.getConsumer());
548
549 // Drop trailing matches.
550 while (Path.back() == DC_match)
551 Path.pop_back();
552
553 // Skip leading matches.
554 SmallVectorImpl<char>::iterator
555 PI = Path.begin(), PE = Path.end();
556 while (PI != PE && *PI == DC_match) {
557 unify(&*LI, &*RI);
558 ++PI, ++LI, ++RI;
559 }
560
561 for (; PI != PE; ++PI) {
562 switch (static_cast(*PI)) {
563 case DC_match:
564 assert(LI != LE && RI != RE);
565 {
566 Instruction *L = &*LI, *R = &*RI;
567 unify(L, R);
568 Diff.addMatch(L, R);
569 }
570 ++LI; ++RI;
571 break;
572
573 case DC_left:
574 assert(LI != LE);
575 Diff.addLeft(&*LI);
576 ++LI;
577 break;
578
579 case DC_right:
580 assert(RI != RE);
581 Diff.addRight(&*RI);
582 ++RI;
583 break;
584 }
585 }
586
587 // Finishing unifying and complaining about the tails of the block,

--- 90 unchanged lines hidden ---