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/Function.h"
18#include "llvm/Instructions.h"
19#include "llvm/Module.h"
20#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/DenseSet.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/ADT/StringRef.h"
24#include "llvm/ADT/StringSet.h"

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

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

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

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

--- 90 unchanged lines hidden ---