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
| 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"
|
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"
25#include "llvm/Support/CallSite.h"
26#include "llvm/Support/CFG.h"
27#include "llvm/Support/ErrorHandling.h"
28#include "llvm/Support/raw_ostream.h"
29#include "llvm/Support/type_traits.h"
30
31#include <utility>
32
33using namespace llvm;
34
35namespace {
36
37/// A priority queue, implemented as a heap.
38template <class T, class Sorter, unsigned InlineCapacity>
39class PriorityQueue {
40 Sorter Precedes;
41 llvm::SmallVector<T, InlineCapacity> Storage;
42
43public:
44 PriorityQueue(const Sorter &Precedes) : Precedes(Precedes) {}
45
46 /// Checks whether the heap is empty.
47 bool empty() const { return Storage.empty(); }
48
49 /// Insert a new value on the heap.
50 void insert(const T &V) {
51 unsigned Index = Storage.size();
52 Storage.push_back(V);
53 if (Index == 0) return;
54
55 T *data = Storage.data();
56 while (true) {
57 unsigned Target = (Index + 1) / 2 - 1;
58 if (!Precedes(data[Index], data[Target])) return;
59 std::swap(data[Index], data[Target]);
60 if (Target == 0) return;
61 Index = Target;
62 }
63 }
64
65 /// Remove the minimum value in the heap. Only valid on a non-empty heap.
66 T remove_min() {
67 assert(!empty());
68 T tmp = Storage[0];
69
70 unsigned NewSize = Storage.size() - 1;
71 if (NewSize) {
72 // Move the slot at the end to the beginning.
73 if (isPodLike<T>::value)
74 Storage[0] = Storage[NewSize];
75 else
76 std::swap(Storage[0], Storage[NewSize]);
77
78 // Bubble the root up as necessary.
79 unsigned Index = 0;
80 while (true) {
81 // With a 1-based index, the children would be Index*2 and Index*2+1.
82 unsigned R = (Index + 1) * 2;
83 unsigned L = R - 1;
84
85 // If R is out of bounds, we're done after this in any case.
86 if (R >= NewSize) {
87 // If L is also out of bounds, we're done immediately.
88 if (L >= NewSize) break;
89
90 // Otherwise, test whether we should swap L and Index.
91 if (Precedes(Storage[L], Storage[Index]))
92 std::swap(Storage[L], Storage[Index]);
93 break;
94 }
95
96 // Otherwise, we need to compare with the smaller of L and R.
97 // Prefer R because it's closer to the end of the array.
98 unsigned IndexToTest = (Precedes(Storage[L], Storage[R]) ? L : R);
99
100 // If Index is >= the min of L and R, then heap ordering is restored.
101 if (!Precedes(Storage[IndexToTest], Storage[Index]))
102 break;
103
104 // Otherwise, keep bubbling up.
105 std::swap(Storage[IndexToTest], Storage[Index]);
106 Index = IndexToTest;
107 }
108 }
109 Storage.pop_back();
110
111 return tmp;
112 }
113};
114
115/// A function-scope difference engine.
116class FunctionDifferenceEngine {
117 DifferenceEngine &Engine;
118
119 /// The current mapping from old local values to new local values.
120 DenseMap<Value*, Value*> Values;
121
122 /// The current mapping from old blocks to new blocks.
123 DenseMap<BasicBlock*, BasicBlock*> Blocks;
124
125 DenseSet<std::pair<Value*, Value*> > TentativeValues;
126
127 unsigned getUnprocPredCount(BasicBlock *Block) const {
128 unsigned Count = 0;
129 for (pred_iterator I = pred_begin(Block), E = pred_end(Block); I != E; ++I)
130 if (!Blocks.count(*I)) Count++;
131 return Count;
132 }
133
134 typedef std::pair<BasicBlock*, BasicBlock*> BlockPair;
135
136 /// A type which sorts a priority queue by the number of unprocessed
137 /// predecessor blocks it has remaining.
138 ///
139 /// This is actually really expensive to calculate.
140 struct QueueSorter {
141 const FunctionDifferenceEngine &fde;
142 explicit QueueSorter(const FunctionDifferenceEngine &fde) : fde(fde) {}
143
144 bool operator()(const BlockPair &Old, const BlockPair &New) {
145 return fde.getUnprocPredCount(Old.first)
146 < fde.getUnprocPredCount(New.first);
147 }
148 };
149
150 /// A queue of unified blocks to process.
151 PriorityQueue<BlockPair, QueueSorter, 20> Queue;
152
153 /// Try to unify the given two blocks. Enqueues them for processing
154 /// if they haven't already been processed.
155 ///
156 /// Returns true if there was a problem unifying them.
157 bool tryUnify(BasicBlock *L, BasicBlock *R) {
158 BasicBlock *&Ref = Blocks[L];
159
160 if (Ref) {
161 if (Ref == R) return false;
162
163 Engine.logf("successor %l cannot be equivalent to %r; "
164 "it's already equivalent to %r")
165 << L << R << Ref;
166 return true;
167 }
168
169 Ref = R;
170 Queue.insert(BlockPair(L, R));
171 return false;
172 }
173
174 /// Unifies two instructions, given that they're known not to have
175 /// structural differences.
176 void unify(Instruction *L, Instruction *R) {
177 DifferenceEngine::Context C(Engine, L, R);
178
179 bool Result = diff(L, R, true, true);
180 assert(!Result && "structural differences second time around?");
181 (void) Result;
182 if (!L->use_empty())
183 Values[L] = R;
184 }
185
186 void processQueue() {
187 while (!Queue.empty()) {
188 BlockPair Pair = Queue.remove_min();
189 diff(Pair.first, Pair.second);
190 }
191 }
192
193 void diff(BasicBlock *L, BasicBlock *R) {
194 DifferenceEngine::Context C(Engine, L, R);
195
196 BasicBlock::iterator LI = L->begin(), LE = L->end();
197 BasicBlock::iterator RI = R->begin(), RE = R->end();
198
199 llvm::SmallVector<std::pair<Instruction*,Instruction*>, 20> TentativePairs;
200
201 do {
202 assert(LI != LE && RI != RE);
203 Instruction *LeftI = &*LI, *RightI = &*RI;
204
205 // If the instructions differ, start the more sophisticated diff
206 // algorithm at the start of the block.
207 if (diff(LeftI, RightI, false, false)) {
208 TentativeValues.clear();
209 return runBlockDiff(L->begin(), R->begin());
210 }
211
212 // Otherwise, tentatively unify them.
213 if (!LeftI->use_empty())
214 TentativeValues.insert(std::make_pair(LeftI, RightI));
215
216 ++LI, ++RI;
217 } while (LI != LE); // This is sufficient: we can't get equality of
218 // terminators if there are residual instructions.
219
220 // Unify everything in the block, non-tentatively this time.
221 TentativeValues.clear();
222 for (LI = L->begin(), RI = R->begin(); LI != LE; ++LI, ++RI)
223 unify(&*LI, &*RI);
224 }
225
226 bool matchForBlockDiff(Instruction *L, Instruction *R);
227 void runBlockDiff(BasicBlock::iterator LI, BasicBlock::iterator RI);
228
229 bool diffCallSites(CallSite L, CallSite R, bool Complain) {
230 // FIXME: call attributes
231 if (!equivalentAsOperands(L.getCalledValue(), R.getCalledValue())) {
232 if (Complain) Engine.log("called functions differ");
233 return true;
234 }
235 if (L.arg_size() != R.arg_size()) {
236 if (Complain) Engine.log("argument counts differ");
237 return true;
238 }
239 for (unsigned I = 0, E = L.arg_size(); I != E; ++I)
240 if (!equivalentAsOperands(L.getArgument(I), R.getArgument(I))) {
241 if (Complain)
242 Engine.logf("arguments %l and %r differ")
243 << L.getArgument(I) << R.getArgument(I);
244 return true;
245 }
246 return false;
247 }
248
249 bool diff(Instruction *L, Instruction *R, bool Complain, bool TryUnify) {
250 // FIXME: metadata (if Complain is set)
251
252 // Different opcodes always imply different operations.
253 if (L->getOpcode() != R->getOpcode()) {
254 if (Complain) Engine.log("different instruction types");
255 return true;
256 }
257
258 if (isa<CmpInst>(L)) {
259 if (cast<CmpInst>(L)->getPredicate()
260 != cast<CmpInst>(R)->getPredicate()) {
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
| 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"
26#include "llvm/Support/CallSite.h"
27#include "llvm/Support/CFG.h"
28#include "llvm/Support/ErrorHandling.h"
29#include "llvm/Support/raw_ostream.h"
30#include "llvm/Support/type_traits.h"
31
32#include <utility>
33
34using namespace llvm;
35
36namespace {
37
38/// A priority queue, implemented as a heap.
39template <class T, class Sorter, unsigned InlineCapacity>
40class PriorityQueue {
41 Sorter Precedes;
42 llvm::SmallVector<T, InlineCapacity> Storage;
43
44public:
45 PriorityQueue(const Sorter &Precedes) : Precedes(Precedes) {}
46
47 /// Checks whether the heap is empty.
48 bool empty() const { return Storage.empty(); }
49
50 /// Insert a new value on the heap.
51 void insert(const T &V) {
52 unsigned Index = Storage.size();
53 Storage.push_back(V);
54 if (Index == 0) return;
55
56 T *data = Storage.data();
57 while (true) {
58 unsigned Target = (Index + 1) / 2 - 1;
59 if (!Precedes(data[Index], data[Target])) return;
60 std::swap(data[Index], data[Target]);
61 if (Target == 0) return;
62 Index = Target;
63 }
64 }
65
66 /// Remove the minimum value in the heap. Only valid on a non-empty heap.
67 T remove_min() {
68 assert(!empty());
69 T tmp = Storage[0];
70
71 unsigned NewSize = Storage.size() - 1;
72 if (NewSize) {
73 // Move the slot at the end to the beginning.
74 if (isPodLike<T>::value)
75 Storage[0] = Storage[NewSize];
76 else
77 std::swap(Storage[0], Storage[NewSize]);
78
79 // Bubble the root up as necessary.
80 unsigned Index = 0;
81 while (true) {
82 // With a 1-based index, the children would be Index*2 and Index*2+1.
83 unsigned R = (Index + 1) * 2;
84 unsigned L = R - 1;
85
86 // If R is out of bounds, we're done after this in any case.
87 if (R >= NewSize) {
88 // If L is also out of bounds, we're done immediately.
89 if (L >= NewSize) break;
90
91 // Otherwise, test whether we should swap L and Index.
92 if (Precedes(Storage[L], Storage[Index]))
93 std::swap(Storage[L], Storage[Index]);
94 break;
95 }
96
97 // Otherwise, we need to compare with the smaller of L and R.
98 // Prefer R because it's closer to the end of the array.
99 unsigned IndexToTest = (Precedes(Storage[L], Storage[R]) ? L : R);
100
101 // If Index is >= the min of L and R, then heap ordering is restored.
102 if (!Precedes(Storage[IndexToTest], Storage[Index]))
103 break;
104
105 // Otherwise, keep bubbling up.
106 std::swap(Storage[IndexToTest], Storage[Index]);
107 Index = IndexToTest;
108 }
109 }
110 Storage.pop_back();
111
112 return tmp;
113 }
114};
115
116/// A function-scope difference engine.
117class FunctionDifferenceEngine {
118 DifferenceEngine &Engine;
119
120 /// The current mapping from old local values to new local values.
121 DenseMap<Value*, Value*> Values;
122
123 /// The current mapping from old blocks to new blocks.
124 DenseMap<BasicBlock*, BasicBlock*> Blocks;
125
126 DenseSet<std::pair<Value*, Value*> > TentativeValues;
127
128 unsigned getUnprocPredCount(BasicBlock *Block) const {
129 unsigned Count = 0;
130 for (pred_iterator I = pred_begin(Block), E = pred_end(Block); I != E; ++I)
131 if (!Blocks.count(*I)) Count++;
132 return Count;
133 }
134
135 typedef std::pair<BasicBlock*, BasicBlock*> BlockPair;
136
137 /// A type which sorts a priority queue by the number of unprocessed
138 /// predecessor blocks it has remaining.
139 ///
140 /// This is actually really expensive to calculate.
141 struct QueueSorter {
142 const FunctionDifferenceEngine &fde;
143 explicit QueueSorter(const FunctionDifferenceEngine &fde) : fde(fde) {}
144
145 bool operator()(const BlockPair &Old, const BlockPair &New) {
146 return fde.getUnprocPredCount(Old.first)
147 < fde.getUnprocPredCount(New.first);
148 }
149 };
150
151 /// A queue of unified blocks to process.
152 PriorityQueue<BlockPair, QueueSorter, 20> Queue;
153
154 /// Try to unify the given two blocks. Enqueues them for processing
155 /// if they haven't already been processed.
156 ///
157 /// Returns true if there was a problem unifying them.
158 bool tryUnify(BasicBlock *L, BasicBlock *R) {
159 BasicBlock *&Ref = Blocks[L];
160
161 if (Ref) {
162 if (Ref == R) return false;
163
164 Engine.logf("successor %l cannot be equivalent to %r; "
165 "it's already equivalent to %r")
166 << L << R << Ref;
167 return true;
168 }
169
170 Ref = R;
171 Queue.insert(BlockPair(L, R));
172 return false;
173 }
174
175 /// Unifies two instructions, given that they're known not to have
176 /// structural differences.
177 void unify(Instruction *L, Instruction *R) {
178 DifferenceEngine::Context C(Engine, L, R);
179
180 bool Result = diff(L, R, true, true);
181 assert(!Result && "structural differences second time around?");
182 (void) Result;
183 if (!L->use_empty())
184 Values[L] = R;
185 }
186
187 void processQueue() {
188 while (!Queue.empty()) {
189 BlockPair Pair = Queue.remove_min();
190 diff(Pair.first, Pair.second);
191 }
192 }
193
194 void diff(BasicBlock *L, BasicBlock *R) {
195 DifferenceEngine::Context C(Engine, L, R);
196
197 BasicBlock::iterator LI = L->begin(), LE = L->end();
198 BasicBlock::iterator RI = R->begin(), RE = R->end();
199
200 llvm::SmallVector<std::pair<Instruction*,Instruction*>, 20> TentativePairs;
201
202 do {
203 assert(LI != LE && RI != RE);
204 Instruction *LeftI = &*LI, *RightI = &*RI;
205
206 // If the instructions differ, start the more sophisticated diff
207 // algorithm at the start of the block.
208 if (diff(LeftI, RightI, false, false)) {
209 TentativeValues.clear();
210 return runBlockDiff(L->begin(), R->begin());
211 }
212
213 // Otherwise, tentatively unify them.
214 if (!LeftI->use_empty())
215 TentativeValues.insert(std::make_pair(LeftI, RightI));
216
217 ++LI, ++RI;
218 } while (LI != LE); // This is sufficient: we can't get equality of
219 // terminators if there are residual instructions.
220
221 // Unify everything in the block, non-tentatively this time.
222 TentativeValues.clear();
223 for (LI = L->begin(), RI = R->begin(); LI != LE; ++LI, ++RI)
224 unify(&*LI, &*RI);
225 }
226
227 bool matchForBlockDiff(Instruction *L, Instruction *R);
228 void runBlockDiff(BasicBlock::iterator LI, BasicBlock::iterator RI);
229
230 bool diffCallSites(CallSite L, CallSite R, bool Complain) {
231 // FIXME: call attributes
232 if (!equivalentAsOperands(L.getCalledValue(), R.getCalledValue())) {
233 if (Complain) Engine.log("called functions differ");
234 return true;
235 }
236 if (L.arg_size() != R.arg_size()) {
237 if (Complain) Engine.log("argument counts differ");
238 return true;
239 }
240 for (unsigned I = 0, E = L.arg_size(); I != E; ++I)
241 if (!equivalentAsOperands(L.getArgument(I), R.getArgument(I))) {
242 if (Complain)
243 Engine.logf("arguments %l and %r differ")
244 << L.getArgument(I) << R.getArgument(I);
245 return true;
246 }
247 return false;
248 }
249
250 bool diff(Instruction *L, Instruction *R, bool Complain, bool TryUnify) {
251 // FIXME: metadata (if Complain is set)
252
253 // Different opcodes always imply different operations.
254 if (L->getOpcode() != R->getOpcode()) {
255 if (Complain) Engine.log("different instruction types");
256 return true;
257 }
258
259 if (isa<CmpInst>(L)) {
260 if (cast<CmpInst>(L)->getPredicate()
261 != cast<CmpInst>(R)->getPredicate()) {
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
|
269 // This is really wierd; type uniquing is broken?
| 270 // This is really weird; 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
278 // Terminators.
279 } else if (isa<InvokeInst>(L)) {
280 InvokeInst *LI = cast<InvokeInst>(L);
281 InvokeInst *RI = cast<InvokeInst>(R);
282 if (diffCallSites(CallSite(LI), CallSite(RI), Complain))
283 return true;
284
285 if (TryUnify) {
286 tryUnify(LI->getNormalDest(), RI->getNormalDest());
287 tryUnify(LI->getUnwindDest(), RI->getUnwindDest());
288 }
289 return false;
290
291 } else if (isa<BranchInst>(L)) {
292 BranchInst *LI = cast<BranchInst>(L);
293 BranchInst *RI = cast<BranchInst>(R);
294 if (LI->isConditional() != RI->isConditional()) {
295 if (Complain) Engine.log("branch conditionality differs");
296 return true;
297 }
298
299 if (LI->isConditional()) {
300 if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) {
301 if (Complain) Engine.log("branch conditions differ");
302 return true;
303 }
304 if (TryUnify) tryUnify(LI->getSuccessor(1), RI->getSuccessor(1));
305 }
306 if (TryUnify) tryUnify(LI->getSuccessor(0), RI->getSuccessor(0));
307 return false;
308
309 } else if (isa<SwitchInst>(L)) {
310 SwitchInst *LI = cast<SwitchInst>(L);
311 SwitchInst *RI = cast<SwitchInst>(R);
312 if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) {
313 if (Complain) Engine.log("switch conditions differ");
314 return true;
315 }
316 if (TryUnify) tryUnify(LI->getDefaultDest(), RI->getDefaultDest());
317
318 bool Difference = false;
319
320 DenseMap<ConstantInt*,BasicBlock*> LCases;
321 for (unsigned I = 1, E = LI->getNumCases(); I != E; ++I)
322 LCases[LI->getCaseValue(I)] = LI->getSuccessor(I);
323 for (unsigned I = 1, E = RI->getNumCases(); I != E; ++I) {
324 ConstantInt *CaseValue = RI->getCaseValue(I);
325 BasicBlock *LCase = LCases[CaseValue];
326 if (LCase) {
327 if (TryUnify) tryUnify(LCase, RI->getSuccessor(I));
328 LCases.erase(CaseValue);
329 } else if (!Difference) {
330 if (Complain)
331 Engine.logf("right switch has extra case %r") << CaseValue;
332 Difference = true;
333 }
334 }
335 if (!Difference)
336 for (DenseMap<ConstantInt*,BasicBlock*>::iterator
337 I = LCases.begin(), E = LCases.end(); I != E; ++I) {
338 if (Complain)
339 Engine.logf("left switch has extra case %l") << I->first;
340 Difference = true;
341 }
342 return Difference;
343 } else if (isa<UnreachableInst>(L)) {
344 return false;
345 }
346
347 if (L->getNumOperands() != R->getNumOperands()) {
348 if (Complain) Engine.log("instructions have different operand counts");
349 return true;
350 }
351
352 for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) {
353 Value *LO = L->getOperand(I), *RO = R->getOperand(I);
354 if (!equivalentAsOperands(LO, RO)) {
355 if (Complain) Engine.logf("operands %l and %r differ") << LO << RO;
356 return true;
357 }
358 }
359
360 return false;
361 }
362
363 bool equivalentAsOperands(Constant *L, Constant *R) {
364 // Use equality as a preliminary filter.
365 if (L == R)
366 return true;
367
368 if (L->getValueID() != R->getValueID())
369 return false;
370
371 // Ask the engine about global values.
372 if (isa<GlobalValue>(L))
373 return Engine.equivalentAsOperands(cast<GlobalValue>(L),
374 cast<GlobalValue>(R));
375
376 // Compare constant expressions structurally.
377 if (isa<ConstantExpr>(L))
378 return equivalentAsOperands(cast<ConstantExpr>(L),
379 cast<ConstantExpr>(R));
380
381 // Nulls of the "same type" don't always actually have the same
382 // type; I don't know why. Just white-list them.
383 if (isa<ConstantPointerNull>(L))
384 return true;
385
386 // Block addresses only match if we've already encountered the
387 // block. FIXME: tentative matches?
388 if (isa<BlockAddress>(L))
389 return Blocks[cast<BlockAddress>(L)->getBasicBlock()]
390 == cast<BlockAddress>(R)->getBasicBlock();
391
392 return false;
393 }
394
395 bool equivalentAsOperands(ConstantExpr *L, ConstantExpr *R) {
396 if (L == R)
397 return true;
398 if (L->getOpcode() != R->getOpcode())
399 return false;
400
401 switch (L->getOpcode()) {
402 case Instruction::ICmp:
403 case Instruction::FCmp:
404 if (L->getPredicate() != R->getPredicate())
405 return false;
406 break;
407
408 case Instruction::GetElementPtr:
409 // FIXME: inbounds?
410 break;
411
412 default:
413 break;
414 }
415
416 if (L->getNumOperands() != R->getNumOperands())
417 return false;
418
419 for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I)
420 if (!equivalentAsOperands(L->getOperand(I), R->getOperand(I)))
421 return false;
422
423 return true;
424 }
425
426 bool equivalentAsOperands(Value *L, Value *R) {
427 // Fall out if the values have different kind.
428 // This possibly shouldn't take priority over oracles.
429 if (L->getValueID() != R->getValueID())
430 return false;
431
432 // Value subtypes: Argument, Constant, Instruction, BasicBlock,
433 // InlineAsm, MDNode, MDString, PseudoSourceValue
434
435 if (isa<Constant>(L))
436 return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R));
437
438 if (isa<Instruction>(L))
439 return Values[L] == R || TentativeValues.count(std::make_pair(L, R));
440
441 if (isa<Argument>(L))
442 return Values[L] == R;
443
444 if (isa<BasicBlock>(L))
445 return Blocks[cast<BasicBlock>(L)] != R;
446
447 // Pretend everything else is identical.
448 return true;
449 }
450
451 // Avoid a gcc warning about accessing 'this' in an initializer.
452 FunctionDifferenceEngine *this_() { return this; }
453
454public:
455 FunctionDifferenceEngine(DifferenceEngine &Engine) :
456 Engine(Engine), Queue(QueueSorter(*this_())) {}
457
458 void diff(Function *L, Function *R) {
459 if (L->arg_size() != R->arg_size())
460 Engine.log("different argument counts");
461
462 // Map the arguments.
463 for (Function::arg_iterator
464 LI = L->arg_begin(), LE = L->arg_end(),
465 RI = R->arg_begin(), RE = R->arg_end();
466 LI != LE && RI != RE; ++LI, ++RI)
467 Values[&*LI] = &*RI;
468
469 tryUnify(&*L->begin(), &*R->begin());
470 processQueue();
471 }
472};
473
474struct DiffEntry {
475 DiffEntry() : Cost(0) {}
476
477 unsigned Cost;
478 llvm::SmallVector<char, 8> Path; // actually of DifferenceEngine::DiffChange
479};
480
481bool FunctionDifferenceEngine::matchForBlockDiff(Instruction *L,
482 Instruction *R) {
483 return !diff(L, R, false, false);
484}
485
486void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart,
487 BasicBlock::iterator RStart) {
488 BasicBlock::iterator LE = LStart->getParent()->end();
489 BasicBlock::iterator RE = RStart->getParent()->end();
490
491 unsigned NL = std::distance(LStart, LE);
492
493 SmallVector<DiffEntry, 20> Paths1(NL+1);
494 SmallVector<DiffEntry, 20> Paths2(NL+1);
495
496 DiffEntry *Cur = Paths1.data();
497 DiffEntry *Next = Paths2.data();
498
499 const unsigned LeftCost = 2;
500 const unsigned RightCost = 2;
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)
| 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
279 // Terminators.
280 } else if (isa<InvokeInst>(L)) {
281 InvokeInst *LI = cast<InvokeInst>(L);
282 InvokeInst *RI = cast<InvokeInst>(R);
283 if (diffCallSites(CallSite(LI), CallSite(RI), Complain))
284 return true;
285
286 if (TryUnify) {
287 tryUnify(LI->getNormalDest(), RI->getNormalDest());
288 tryUnify(LI->getUnwindDest(), RI->getUnwindDest());
289 }
290 return false;
291
292 } else if (isa<BranchInst>(L)) {
293 BranchInst *LI = cast<BranchInst>(L);
294 BranchInst *RI = cast<BranchInst>(R);
295 if (LI->isConditional() != RI->isConditional()) {
296 if (Complain) Engine.log("branch conditionality differs");
297 return true;
298 }
299
300 if (LI->isConditional()) {
301 if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) {
302 if (Complain) Engine.log("branch conditions differ");
303 return true;
304 }
305 if (TryUnify) tryUnify(LI->getSuccessor(1), RI->getSuccessor(1));
306 }
307 if (TryUnify) tryUnify(LI->getSuccessor(0), RI->getSuccessor(0));
308 return false;
309
310 } else if (isa<SwitchInst>(L)) {
311 SwitchInst *LI = cast<SwitchInst>(L);
312 SwitchInst *RI = cast<SwitchInst>(R);
313 if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) {
314 if (Complain) Engine.log("switch conditions differ");
315 return true;
316 }
317 if (TryUnify) tryUnify(LI->getDefaultDest(), RI->getDefaultDest());
318
319 bool Difference = false;
320
321 DenseMap<ConstantInt*,BasicBlock*> LCases;
322 for (unsigned I = 1, E = LI->getNumCases(); I != E; ++I)
323 LCases[LI->getCaseValue(I)] = LI->getSuccessor(I);
324 for (unsigned I = 1, E = RI->getNumCases(); I != E; ++I) {
325 ConstantInt *CaseValue = RI->getCaseValue(I);
326 BasicBlock *LCase = LCases[CaseValue];
327 if (LCase) {
328 if (TryUnify) tryUnify(LCase, RI->getSuccessor(I));
329 LCases.erase(CaseValue);
330 } else if (!Difference) {
331 if (Complain)
332 Engine.logf("right switch has extra case %r") << CaseValue;
333 Difference = true;
334 }
335 }
336 if (!Difference)
337 for (DenseMap<ConstantInt*,BasicBlock*>::iterator
338 I = LCases.begin(), E = LCases.end(); I != E; ++I) {
339 if (Complain)
340 Engine.logf("left switch has extra case %l") << I->first;
341 Difference = true;
342 }
343 return Difference;
344 } else if (isa<UnreachableInst>(L)) {
345 return false;
346 }
347
348 if (L->getNumOperands() != R->getNumOperands()) {
349 if (Complain) Engine.log("instructions have different operand counts");
350 return true;
351 }
352
353 for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) {
354 Value *LO = L->getOperand(I), *RO = R->getOperand(I);
355 if (!equivalentAsOperands(LO, RO)) {
356 if (Complain) Engine.logf("operands %l and %r differ") << LO << RO;
357 return true;
358 }
359 }
360
361 return false;
362 }
363
364 bool equivalentAsOperands(Constant *L, Constant *R) {
365 // Use equality as a preliminary filter.
366 if (L == R)
367 return true;
368
369 if (L->getValueID() != R->getValueID())
370 return false;
371
372 // Ask the engine about global values.
373 if (isa<GlobalValue>(L))
374 return Engine.equivalentAsOperands(cast<GlobalValue>(L),
375 cast<GlobalValue>(R));
376
377 // Compare constant expressions structurally.
378 if (isa<ConstantExpr>(L))
379 return equivalentAsOperands(cast<ConstantExpr>(L),
380 cast<ConstantExpr>(R));
381
382 // Nulls of the "same type" don't always actually have the same
383 // type; I don't know why. Just white-list them.
384 if (isa<ConstantPointerNull>(L))
385 return true;
386
387 // Block addresses only match if we've already encountered the
388 // block. FIXME: tentative matches?
389 if (isa<BlockAddress>(L))
390 return Blocks[cast<BlockAddress>(L)->getBasicBlock()]
391 == cast<BlockAddress>(R)->getBasicBlock();
392
393 return false;
394 }
395
396 bool equivalentAsOperands(ConstantExpr *L, ConstantExpr *R) {
397 if (L == R)
398 return true;
399 if (L->getOpcode() != R->getOpcode())
400 return false;
401
402 switch (L->getOpcode()) {
403 case Instruction::ICmp:
404 case Instruction::FCmp:
405 if (L->getPredicate() != R->getPredicate())
406 return false;
407 break;
408
409 case Instruction::GetElementPtr:
410 // FIXME: inbounds?
411 break;
412
413 default:
414 break;
415 }
416
417 if (L->getNumOperands() != R->getNumOperands())
418 return false;
419
420 for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I)
421 if (!equivalentAsOperands(L->getOperand(I), R->getOperand(I)))
422 return false;
423
424 return true;
425 }
426
427 bool equivalentAsOperands(Value *L, Value *R) {
428 // Fall out if the values have different kind.
429 // This possibly shouldn't take priority over oracles.
430 if (L->getValueID() != R->getValueID())
431 return false;
432
433 // Value subtypes: Argument, Constant, Instruction, BasicBlock,
434 // InlineAsm, MDNode, MDString, PseudoSourceValue
435
436 if (isa<Constant>(L))
437 return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R));
438
439 if (isa<Instruction>(L))
440 return Values[L] == R || TentativeValues.count(std::make_pair(L, R));
441
442 if (isa<Argument>(L))
443 return Values[L] == R;
444
445 if (isa<BasicBlock>(L))
446 return Blocks[cast<BasicBlock>(L)] != R;
447
448 // Pretend everything else is identical.
449 return true;
450 }
451
452 // Avoid a gcc warning about accessing 'this' in an initializer.
453 FunctionDifferenceEngine *this_() { return this; }
454
455public:
456 FunctionDifferenceEngine(DifferenceEngine &Engine) :
457 Engine(Engine), Queue(QueueSorter(*this_())) {}
458
459 void diff(Function *L, Function *R) {
460 if (L->arg_size() != R->arg_size())
461 Engine.log("different argument counts");
462
463 // Map the arguments.
464 for (Function::arg_iterator
465 LI = L->arg_begin(), LE = L->arg_end(),
466 RI = R->arg_begin(), RE = R->arg_end();
467 LI != LE && RI != RE; ++LI, ++RI)
468 Values[&*LI] = &*RI;
469
470 tryUnify(&*L->begin(), &*R->begin());
471 processQueue();
472 }
473};
474
475struct DiffEntry {
476 DiffEntry() : Cost(0) {}
477
478 unsigned Cost;
479 llvm::SmallVector<char, 8> Path; // actually of DifferenceEngine::DiffChange
480};
481
482bool FunctionDifferenceEngine::matchForBlockDiff(Instruction *L,
483 Instruction *R) {
484 return !diff(L, R, false, false);
485}
486
487void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart,
488 BasicBlock::iterator RStart) {
489 BasicBlock::iterator LE = LStart->getParent()->end();
490 BasicBlock::iterator RE = RStart->getParent()->end();
491
492 unsigned NL = std::distance(LStart, LE);
493
494 SmallVector<DiffEntry, 20> Paths1(NL+1);
495 SmallVector<DiffEntry, 20> Paths2(NL+1);
496
497 DiffEntry *Cur = Paths1.data();
498 DiffEntry *Next = Paths2.data();
499
500 const unsigned LeftCost = 2;
501 const unsigned RightCost = 2;
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)
|
509 Cur[I].Path.push_back(DifferenceEngine::DC_left);
| 510 Cur[I].Path.push_back(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;
| 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;
|
516 Next[0].Path.push_back(DifferenceEngine::DC_right);
| 517 Next[0].Path.push_back(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;
| 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;
|
523 Next[Index].Path.push_back(DifferenceEngine::DC_match);
| 524 Next[Index].Path.push_back(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;
| 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;
|
528 Next[Index].Path.push_back(DifferenceEngine::DC_left);
| 529 Next[Index].Path.push_back(DC_left);
|
529 } else {
530 Next[Index] = Cur[Index];
531 Next[Index].Cost += RightCost;
| 530 } else {
531 Next[Index] = Cur[Index];
532 Next[Index].Cost += RightCost;
|
532 Next[Index].Path.push_back(DifferenceEngine::DC_right);
| 533 Next[Index].Path.push_back(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
| 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
|
546 DifferenceEngine::DiffLogBuilder Diff(Engine);
| 547 DiffLogBuilder Diff(Engine.getConsumer());
|
547
548 // Drop trailing matches.
| 548
549 // Drop trailing matches.
|
549 while (Path.back() == DifferenceEngine::DC_match)
| 550 while (Path.back() == DC_match)
|
550 Path.pop_back();
551
552 // Skip leading matches.
553 SmallVectorImpl<char>::iterator
554 PI = Path.begin(), PE = Path.end();
| 551 Path.pop_back();
552
553 // Skip leading matches.
554 SmallVectorImpl<char>::iterator
555 PI = Path.begin(), PE = Path.end();
|
555 while (PI != PE && *PI == DifferenceEngine::DC_match) {
| 556 while (PI != PE && *PI == DC_match) {
|
556 unify(&*LI, &*RI);
557 ++PI, ++LI, ++RI;
558 }
559
560 for (; PI != PE; ++PI) {
| 557 unify(&*LI, &*RI);
558 ++PI, ++LI, ++RI;
559 }
560
561 for (; PI != PE; ++PI) {
|
561 switch (static_cast<DifferenceEngine::DiffChange>(*PI)) {
562 case DifferenceEngine::DC_match:
| 562 switch (static_cast(*PI)) {
563 case 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
| 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
|
572 case DifferenceEngine::DC_left:
| 573 case DC_left:
|
573 assert(LI != LE);
574 Diff.addLeft(&*LI);
575 ++LI;
576 break;
577
| 574 assert(LI != LE);
575 Diff.addLeft(&*LI);
576 ++LI;
577 break;
578
|
578 case DifferenceEngine::DC_right:
| 579 case 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,
587 // which should be matches all the way through.
588 while (LI != LE) {
589 assert(RI != RE);
590 unify(&*LI, &*RI);
591 ++LI, ++RI;
592 }
593
594 // If the terminators have different kinds, but one is an invoke and the
595 // other is an unconditional branch immediately following a call, unify
596 // the results and the destinations.
597 TerminatorInst *LTerm = LStart->getParent()->getTerminator();
598 TerminatorInst *RTerm = RStart->getParent()->getTerminator();
599 if (isa<BranchInst>(LTerm) && isa<InvokeInst>(RTerm)) {
600 if (cast<BranchInst>(LTerm)->isConditional()) return;
601 BasicBlock::iterator I = LTerm;
602 if (I == LStart->getParent()->begin()) return;
603 --I;
604 if (!isa<CallInst>(*I)) return;
605 CallInst *LCall = cast<CallInst>(&*I);
606 InvokeInst *RInvoke = cast<InvokeInst>(RTerm);
607 if (!equivalentAsOperands(LCall->getCalledValue(), RInvoke->getCalledValue()))
608 return;
609 if (!LCall->use_empty())
610 Values[LCall] = RInvoke;
611 tryUnify(LTerm->getSuccessor(0), RInvoke->getNormalDest());
612 } else if (isa<InvokeInst>(LTerm) && isa<BranchInst>(RTerm)) {
613 if (cast<BranchInst>(RTerm)->isConditional()) return;
614 BasicBlock::iterator I = RTerm;
615 if (I == RStart->getParent()->begin()) return;
616 --I;
617 if (!isa<CallInst>(*I)) return;
618 CallInst *RCall = cast<CallInst>(I);
619 InvokeInst *LInvoke = cast<InvokeInst>(LTerm);
620 if (!equivalentAsOperands(LInvoke->getCalledValue(), RCall->getCalledValue()))
621 return;
622 if (!LInvoke->use_empty())
623 Values[LInvoke] = RCall;
624 tryUnify(LInvoke->getNormalDest(), RTerm->getSuccessor(0));
625 }
626}
627
628}
629
630void DifferenceEngine::diff(Function *L, Function *R) {
631 Context C(*this, L, R);
632
633 // FIXME: types
634 // FIXME: attributes and CC
635 // FIXME: parameter attributes
636
637 // If both are declarations, we're done.
638 if (L->empty() && R->empty())
639 return;
640 else if (L->empty())
641 log("left function is declaration, right function is definition");
642 else if (R->empty())
643 log("right function is declaration, left function is definition");
644 else
645 FunctionDifferenceEngine(*this).diff(L, R);
646}
647
648void DifferenceEngine::diff(Module *L, Module *R) {
649 StringSet<> LNames;
650 SmallVector<std::pair<Function*,Function*>, 20> Queue;
651
652 for (Module::iterator I = L->begin(), E = L->end(); I != E; ++I) {
653 Function *LFn = &*I;
654 LNames.insert(LFn->getName());
655
656 if (Function *RFn = R->getFunction(LFn->getName()))
657 Queue.push_back(std::make_pair(LFn, RFn));
658 else
659 logf("function %l exists only in left module") << LFn;
660 }
661
662 for (Module::iterator I = R->begin(), E = R->end(); I != E; ++I) {
663 Function *RFn = &*I;
664 if (!LNames.count(RFn->getName()))
665 logf("function %r exists only in right module") << RFn;
666 }
667
668 for (SmallVectorImpl<std::pair<Function*,Function*> >::iterator
669 I = Queue.begin(), E = Queue.end(); I != E; ++I)
670 diff(I->first, I->second);
671}
672
673bool DifferenceEngine::equivalentAsOperands(GlobalValue *L, GlobalValue *R) {
674 if (globalValueOracle) return (*globalValueOracle)(L, R);
675 return L->getName() == R->getName();
676}
| 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,
588 // which should be matches all the way through.
589 while (LI != LE) {
590 assert(RI != RE);
591 unify(&*LI, &*RI);
592 ++LI, ++RI;
593 }
594
595 // If the terminators have different kinds, but one is an invoke and the
596 // other is an unconditional branch immediately following a call, unify
597 // the results and the destinations.
598 TerminatorInst *LTerm = LStart->getParent()->getTerminator();
599 TerminatorInst *RTerm = RStart->getParent()->getTerminator();
600 if (isa<BranchInst>(LTerm) && isa<InvokeInst>(RTerm)) {
601 if (cast<BranchInst>(LTerm)->isConditional()) return;
602 BasicBlock::iterator I = LTerm;
603 if (I == LStart->getParent()->begin()) return;
604 --I;
605 if (!isa<CallInst>(*I)) return;
606 CallInst *LCall = cast<CallInst>(&*I);
607 InvokeInst *RInvoke = cast<InvokeInst>(RTerm);
608 if (!equivalentAsOperands(LCall->getCalledValue(), RInvoke->getCalledValue()))
609 return;
610 if (!LCall->use_empty())
611 Values[LCall] = RInvoke;
612 tryUnify(LTerm->getSuccessor(0), RInvoke->getNormalDest());
613 } else if (isa<InvokeInst>(LTerm) && isa<BranchInst>(RTerm)) {
614 if (cast<BranchInst>(RTerm)->isConditional()) return;
615 BasicBlock::iterator I = RTerm;
616 if (I == RStart->getParent()->begin()) return;
617 --I;
618 if (!isa<CallInst>(*I)) return;
619 CallInst *RCall = cast<CallInst>(I);
620 InvokeInst *LInvoke = cast<InvokeInst>(LTerm);
621 if (!equivalentAsOperands(LInvoke->getCalledValue(), RCall->getCalledValue()))
622 return;
623 if (!LInvoke->use_empty())
624 Values[LInvoke] = RCall;
625 tryUnify(LInvoke->getNormalDest(), RTerm->getSuccessor(0));
626 }
627}
628
629}
630
631void DifferenceEngine::diff(Function *L, Function *R) {
632 Context C(*this, L, R);
633
634 // FIXME: types
635 // FIXME: attributes and CC
636 // FIXME: parameter attributes
637
638 // If both are declarations, we're done.
639 if (L->empty() && R->empty())
640 return;
641 else if (L->empty())
642 log("left function is declaration, right function is definition");
643 else if (R->empty())
644 log("right function is declaration, left function is definition");
645 else
646 FunctionDifferenceEngine(*this).diff(L, R);
647}
648
649void DifferenceEngine::diff(Module *L, Module *R) {
650 StringSet<> LNames;
651 SmallVector<std::pair<Function*,Function*>, 20> Queue;
652
653 for (Module::iterator I = L->begin(), E = L->end(); I != E; ++I) {
654 Function *LFn = &*I;
655 LNames.insert(LFn->getName());
656
657 if (Function *RFn = R->getFunction(LFn->getName()))
658 Queue.push_back(std::make_pair(LFn, RFn));
659 else
660 logf("function %l exists only in left module") << LFn;
661 }
662
663 for (Module::iterator I = R->begin(), E = R->end(); I != E; ++I) {
664 Function *RFn = &*I;
665 if (!LNames.count(RFn->getName()))
666 logf("function %r exists only in right module") << RFn;
667 }
668
669 for (SmallVectorImpl<std::pair<Function*,Function*> >::iterator
670 I = Queue.begin(), E = Queue.end(); I != E; ++I)
671 diff(I->first, I->second);
672}
673
674bool DifferenceEngine::equivalentAsOperands(GlobalValue *L, GlobalValue *R) {
675 if (globalValueOracle) return (*globalValueOracle)(L, R);
676 return L->getName() == R->getName();
677}
|