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 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 --- |