1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
//===-- DifferenceEngine.h - Module comparator ------------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This header defines the interface to the LLVM difference engine,
// which structurally compares functions within a module.
//
//===----------------------------------------------------------------------===//
#ifndef _LLVM_DIFFERENCE_ENGINE_H_
#define _LLVM_DIFFERENCE_ENGINE_H_
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include <utility>
namespace llvm {
class Function;
class GlobalValue;
class Instruction;
class LLVMContext;
class Module;
class Twine;
class Value;
/// A class for performing structural comparisons of LLVM assembly.
class DifferenceEngine {
public:
/// A temporary-object class for building up log messages.
class LogBuilder {
DifferenceEngine &Engine;
/// The use of a stored StringRef here is okay because
/// LogBuilder should be used only as a temporary, and as a
/// temporary it will be destructed before whatever temporary
/// might be initializing this format.
StringRef Format;
SmallVector<Value*, 4> Arguments;
public:
LogBuilder(DifferenceEngine &Engine, StringRef Format)
: Engine(Engine), Format(Format) {}
LogBuilder &operator<<(Value *V) {
Arguments.push_back(V);
return *this;
}
~LogBuilder() {
Engine.consumer.logf(*this);
}
StringRef getFormat() const { return Format; }
unsigned getNumArguments() const { return Arguments.size(); }
Value *getArgument(unsigned I) const { return Arguments[I]; }
};
enum DiffChange { DC_match, DC_left, DC_right };
/// A temporary-object class for building up diff messages.
class DiffLogBuilder {
typedef std::pair<Instruction*,Instruction*> DiffRecord;
SmallVector<DiffRecord, 20> Diff;
DifferenceEngine &Engine;
public:
DiffLogBuilder(DifferenceEngine &Engine) : Engine(Engine) {}
~DiffLogBuilder() { Engine.consumer.logd(*this); }
void addMatch(Instruction *L, Instruction *R) {
Diff.push_back(DiffRecord(L, R));
}
void addLeft(Instruction *L) {
// HACK: VS 2010 has a bug in the stdlib that requires this.
Diff.push_back(DiffRecord(L, DiffRecord::second_type(0)));
}
void addRight(Instruction *R) {
// HACK: VS 2010 has a bug in the stdlib that requires this.
Diff.push_back(DiffRecord(DiffRecord::first_type(0), R));
}
unsigned getNumLines() const { return Diff.size(); }
DiffChange getLineKind(unsigned I) const {
return (Diff[I].first ? (Diff[I].second ? DC_match : DC_left)
: DC_right);
}
Instruction *getLeft(unsigned I) const { return Diff[I].first; }
Instruction *getRight(unsigned I) const { return Diff[I].second; }
};
/// The interface for consumers of difference data.
struct Consumer {
/// Record that a local context has been entered. Left and
/// Right are IR "containers" of some sort which are being
/// considered for structural equivalence: global variables,
/// functions, blocks, instructions, etc.
virtual void enterContext(Value *Left, Value *Right) = 0;
/// Record that a local context has been exited.
virtual void exitContext() = 0;
/// Record a difference within the current context.
virtual void log(StringRef Text) = 0;
/// Record a formatted difference within the current context.
virtual void logf(const LogBuilder &Log) = 0;
/// Record a line-by-line instruction diff.
virtual void logd(const DiffLogBuilder &Log) = 0;
protected:
virtual ~Consumer() {}
};
/// A RAII object for recording the current context.
struct Context {
Context(DifferenceEngine &Engine, Value *L, Value *R) : Engine(Engine) {
Engine.consumer.enterContext(L, R);
}
~Context() {
Engine.consumer.exitContext();
}
private:
DifferenceEngine &Engine;
};
/// An oracle for answering whether two values are equivalent as
/// operands.
struct Oracle {
virtual bool operator()(Value *L, Value *R) = 0;
protected:
virtual ~Oracle() {}
};
DifferenceEngine(LLVMContext &context, Consumer &consumer)
: context(context), consumer(consumer), globalValueOracle(0) {}
void diff(Module *L, Module *R);
void diff(Function *L, Function *R);
void log(StringRef text) {
consumer.log(text);
}
LogBuilder logf(StringRef text) {
return LogBuilder(*this, text);
}
/// Installs an oracle to decide whether two global values are
/// equivalent as operands. Without an oracle, global values are
/// considered equivalent as operands precisely when they have the
/// same name.
void setGlobalValueOracle(Oracle *oracle) {
globalValueOracle = oracle;
}
/// Determines whether two global values are equivalent.
bool equivalentAsOperands(GlobalValue *L, GlobalValue *R);
private:
LLVMContext &context;
Consumer &consumer;
Oracle *globalValueOracle;
};
}
#endif
|