affine_relation.cpp 12.1 KB
Newer Older
1
2
3
#include "affine_relation.h"
#include "llvm/IR/CFG.h"

4
5
#include <set>

6
7
8
9
10
11
12
using namespace llvm;
using namespace std;

namespace pcpo {

// MARK: - Initializers

13
14
15
16
AffineRelation::AffineRelation(Function const& func) {
    index = createVariableIndexMap(func);
    basis = {Matrix<int>(getNumberOfVariables() + 1)};
    isBottom = basis.empty();
17
18
19
}

AffineRelation::AffineRelation(Function const* callee_func, AffineRelation const& state, CallInst const* call) {
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    assert(callee_func->arg_size() == call->getNumArgOperands());
    index = state.index;
    basis = state.basis;

    for (Argument const& arg: callee_func->args()) {
        Value* value = call->getArgOperand(arg.getArgNo());
        if (value->getType()->isIntegerTy()) {
            if (ConstantInt const* c = dyn_cast<ConstantInt>(value)) {
                affineAssignment(&arg, 1, nullptr, c->getSExtValue());
            } else {
                affineAssignment(&arg, 1, value, 0);
            }
        }
    }
Tim Gymnich's avatar
Tim Gymnich committed
34
    isBottom = basis.empty();
35
36
37
38
39
}

// MARK: - AbstractState Interface

void AffineRelation::applyPHINode(BasicBlock const& bb, vector<AffineRelation> pred_values, Instruction const& phi) {
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
    PHINode const* phiNode = dyn_cast<PHINode>(&phi);
    int i = 0;

    for (BasicBlock const* pred_bb: llvm::predecessors(&bb)) {
        auto& incoming_value = *phiNode->getIncomingValueForBlock(pred_bb);
        auto& incoming_state = pred_values[i];

        if (llvm::ConstantInt const* c = llvm::dyn_cast<llvm::ConstantInt>(&incoming_value)) {
            AffineRelation acc = *this;
            acc.affineAssignment(&phi, 1, nullptr, c->getSExtValue());
            merge(Merge_op::UPPER_BOUND, acc);
        } else {
            AffineRelation acc = *this;
            for (auto m: incoming_state.basis) {
                auto val = m.column(index.at(&incoming_value));
                acc.affineAssignment(&phi, 1, &incoming_value, 0);
            }
            merge(Merge_op::UPPER_BOUND, acc);
        }
        i++;
    }
61
62
63
}

void AffineRelation::applyCallInst(Instruction const& inst, BasicBlock const* end_block, AffineRelation const& callee_state) {
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//    std::vector<Matrix> operands;

//     Keep the debug output happy
//    for (llvm::Value const* value : inst.operand_values()) {
//        operands.push_back(getAbstractValue(*value));
//    }

    //iterate through all instructions of it till we find a return statement
    for (Instruction const& iter_inst: *end_block) {
        if (ReturnInst const* ret_inst = llvm::dyn_cast<llvm::ReturnInst>(&iter_inst)) {
            Value const* ret_val = ret_inst->getReturnValue();
            dbgs(4) << "      Found return instruction\n";

            if (callee_state.index.find(ret_val) != callee_state.index.end()) {
                dbgs(4) << "      Return evaluated, merging parameters\n";
                affineAssignment(&inst, 1, ret_val, 0);
            } else {
                dbgs(4) << "      Return not evaluated, setting to bottom\n";
                // TODO: What should we do here
            }
        }
    }
//    debug_output(inst, operands);
87
88
89
}

void AffineRelation::applyReturnInst(Instruction const& inst) {
90
91
92
93
94
95
96
97
    Value const* ret_val = dyn_cast<llvm::ReturnInst>(&inst)->getReturnValue();
    if (ret_val && ret_val->getType()->isIntegerTy()) {
        if (ConstantInt const* c = dyn_cast<ConstantInt>(ret_val)) {
            affineAssignment(&inst, 1, nullptr, c->getSExtValue());
        } else {
            affineAssignment(&inst, 1, ret_val, 0);
        }
    }
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
}

void AffineRelation::applyDefault(Instruction const& inst) {
//    std::vector<LinearEquality> operands;

    if (inst.getNumOperands() != 2) return nonDeterminsticAssignment(&inst);

    // We only deal with integer types
    IntegerType const* type = dyn_cast<IntegerType>(inst.getType());
    if (not type) return nonDeterminsticAssignment(&inst);

    type = dyn_cast<IntegerType>(inst.getOperand(0)->getType());
    if (not type) return nonDeterminsticAssignment(&inst);

    type = dyn_cast<IntegerType>(inst.getOperand(1)->getType());
    if (not type) return nonDeterminsticAssignment(&inst);

115
116
117
118
119
    if (isa<UndefValue>(inst.getOperand(0)) || isa<UndefValue>(inst.getOperand(1))) {
        return nonDeterminsticAssignment(&inst);
    }


120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
//    for (llvm::Value const* value: inst.operand_values()) {
//        operands.push_back(getAbstractValue(*value));
//    }

    switch (inst.getOpcode()) {
        case Instruction::Add:
            return Add(inst);
        case Instruction::Sub:
            return Sub(inst);
        case Instruction::Mul:
            return Mul(inst);
        case Instruction::SDiv:
        case Instruction::UDiv:
        default:
            return nonDeterminsticAssignment(&inst);
    }

//    debug_output(inst, operands);
}

bool AffineRelation::merge(Merge_op::Type op, AffineRelation const& other) {
141
142
143
144
145
146
147
148
149
150
151
152
153
154
    if (other.isBottom) {
        return false;
    } else if (isBottom) {
        // FIXME: is this correct?
        basis = other.basis;
        index = other.index;
        isBottom = false;
        return true;
    }

    switch (op) {
        case Merge_op::UPPER_BOUND: return leastUpperBound(other);
        default: abort();
    }
155
156
157
158
159
}

// MARK: - Lattice Operations

bool AffineRelation::leastUpperBound(AffineRelation rhs) {
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
    assert(getNumberOfVariables() == rhs.getNumberOfVariables());
    vector<Matrix<int>> before = basis;
    vector<vector<int>> vectors;
    vectors.reserve(basis.size() + rhs.basis.size());
    for (Matrix<int> m: basis) {
        vectors.push_back(m.toVector());
    }

    for (Matrix<int> m: rhs.basis) {
        vectors.push_back(m.toVector());
    }
    // FIXME: i think this is transposing it twice. Maybe create a fast path for this kind of thing.
    Matrix<int> combined = Matrix<int>(vectors).transpose();
    Matrix<int> result = Matrix<int>::span(combined);

    basis = result.reshapeColumns(basis.front().getHeight(), basis.front().getHeight());
    // FIXME: figure out a better way to detect changes
177
    return before != basis;
178
179
180
181
}

// MARK: - Assignments

182
183
184
185
186
187
188
void AffineRelation::affineAssignment(Value const* xi, unordered_map<Value const*,int> relations, int constant) {
    Matrix<int> Wr = Matrix<int>(getNumberOfVariables() + 1);
    Wr(0,index.at(xi)) = constant;
    for (auto [variable, factor]: relations) {
        Wr(index.at(variable),index.at(xi)) = factor;
    }

189
    for (Matrix<int>& matrix: basis) {
Tim Gymnich's avatar
Tim Gymnich committed
190
        matrix *= Matrix<int>::span(Wr);
191
192
193
    }
}

194
void AffineRelation::affineAssignment(Value const* xi, int64_t a, Value const* xj, int64_t b) {
195
196
197
198
    if (xj == nullptr) {
        affineAssignment(xi, {}, b);
    } else {
        affineAssignment(xi, {{xj,a}}, b);
199
200
201
202
    }
}

void AffineRelation::nonDeterminsticAssignment(Value const* xi) {
203
204
205
206
207
208
209
210
211
212
213
214
215
216
    Matrix<int> T0 = Matrix<int>(getNumberOfVariables() + 1);
    Matrix<int> T1 = Matrix<int>(getNumberOfVariables() + 1);

    T0(index.at(xi),index.at(xi)) = 0;
    T0(0,index.at(xi)) = 0;

    T1(index.at(xi),index.at(xi)) = 0;
    T1(0,index.at(xi)) = 1;

    for (Matrix<int> matrix: basis) {
        // FIXME: span({T0,T1}) or even leastUpperBound
        matrix *= T0;
        matrix *= T1;
    }
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
}

// MARK: - Abstract Operators

void AffineRelation::Add(Instruction const& inst) {
    auto op1 = inst.getOperand(0);
    auto op2 = inst.getOperand(1);

    // [xi := bj + bk]
    if (isa<ConstantInt>(op1) && (isa<ConstantInt>(op2))) {
        auto b1 = dyn_cast<ConstantInt>(op1);
        auto b2 = dyn_cast<ConstantInt>(op2);
        return affineAssignment(&inst, 1, nullptr, b1->getSExtValue() + b2->getSExtValue() );
        // [xi := b + xj]
    }  else if (isa<ConstantInt>(op1) && isa<Value>(op2)) {
        auto b = dyn_cast<ConstantInt>(op1);
        return affineAssignment(&inst, 1, op2, b->getSExtValue());
        // [xi := xj + b]
    } else if (isa<ConstantInt>(op2) && isa<Value>(op1)) {
        auto b = dyn_cast<ConstantInt>(op2);
        return affineAssignment(&inst, 1, op1, b->getSExtValue());
    } else {
239
        return affineAssignment(&inst, {{op1,1},{op2,1}}, 0);
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
    }
}

void AffineRelation::Sub(Instruction const& inst) {
    auto op1 = inst.getOperand(0);
    auto op2 = inst.getOperand(1);

    // [xi := bj - bk]
    if (isa<ConstantInt>(op1) && (isa<ConstantInt>(op2))) {
        auto b1 = dyn_cast<ConstantInt>(op1);
        auto b2 = dyn_cast<ConstantInt>(op2);
        return affineAssignment(&inst, 1, nullptr, b1->getSExtValue() - b2->getSExtValue() );
    // [xi := b - xj]
    } else if (isa<ConstantInt>(op1) && isa<Value>(op2)) {
        auto b = dyn_cast<ConstantInt>(op1);
        return affineAssignment(&inst, 1, op2, -b->getSExtValue());
    // [xi := xj - b]
    } else if (isa<ConstantInt>(op2) && isa<Value>(op1)) {
        auto b = dyn_cast<ConstantInt>(op2);
        return affineAssignment(&inst, 1, op1, -b->getSExtValue());
    } else {
261
        return affineAssignment(&inst, {{op1,1},{op2,1}}, 0);
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
    }
}

void AffineRelation::Mul(Instruction const& inst) {
    auto op1 = inst.getOperand(0);
    auto op2 = inst.getOperand(1);

    // [xi := aj * ak]
    if (isa<ConstantInt>(op1) && (isa<ConstantInt>(op2))) {
        auto b1 = dyn_cast<ConstantInt>(op1);
        auto b2 = dyn_cast<ConstantInt>(op2);
        return affineAssignment(&inst, 1, nullptr, b1->getSExtValue() * b2->getSExtValue() );
    // [xi := a * xj]
    } else if (isa<ConstantInt>(op1) && isa<Value>(op2)) {
        auto a = dyn_cast<ConstantInt>(op1);
        return affineAssignment(&inst, a->getSExtValue(), op2, 0);
    // [xi := xj * a]
    } else if (isa<ConstantInt>(op2) && isa<Value>(op1)) {
        auto a = dyn_cast<ConstantInt>(op2);
        return affineAssignment(&inst, a->getSExtValue(), op1, 0);
    } else {
        return nonDeterminsticAssignment(&inst);
    }
}

287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
// MARK: - Helpers

unordered_map<Value const*, int> createVariableIndexMap_impl(Function const& func, int& count, set<Function const*> visited_funcs) {
    unordered_map<Value const*, int> map;
    visited_funcs.insert(&func);
    for (BasicBlock const& basic_block: func) {
        for (Instruction const& inst: basic_block) {
            if (isa<IntegerType>(inst.getType()) || isa<ReturnInst>(&inst)) {
                count++;
                map[&inst] = count;
            }
            if (CallInst const* call = dyn_cast<CallInst>(&inst)) {
                Function const* callee_func = call->getCalledFunction();
                if (callee_func->empty()) {
                    continue;
                }
                if (visited_funcs.count(callee_func) == 0) {
                    unordered_map<Value const*, int> callee_map = createVariableIndexMap_impl(*callee_func, count, visited_funcs);
                    map.insert(callee_map.begin(), callee_map.end());
                }
            } 
        }
    }
    return map;
}

unordered_map<Value const*, int> AffineRelation::createVariableIndexMap(Function const& func) {
    int count = 0;
    return createVariableIndexMap_impl(func, count, {});
}

318
319
320
// MARK: - debug output

void AffineRelation::printIncoming(BasicBlock const& bb, raw_ostream& out, int indentation) const {
321
    for (auto m: basis) {
Tim Gymnich's avatar
Tim Gymnich committed
322
        out << llvm::left_justify("", 8);
323
324
        for (auto [val, idx]: index) {
            if (val->hasName()) {
Tim Gymnich's avatar
Tim Gymnich committed
325
                out << llvm::left_justify(val->getName(), 6);
Tim Gymnich's avatar
Tim Gymnich committed
326
            } else {
Tim Gymnich's avatar
Tim Gymnich committed
327
                out << llvm::left_justify("<>", 6);
328
329
330
331
            }
        }
        out << "\n" << m << "\n";
    }
332
333
334
}

void AffineRelation::printOutgoing(BasicBlock const& bb, raw_ostream& out, int indentation) const {
335
    for (auto m: basis) {
Tim Gymnich's avatar
Tim Gymnich committed
336
        out << llvm::left_justify("", 8);
337
338
        for (auto [val, idx]: index) {
            if (val->hasName()) {
Tim Gymnich's avatar
Tim Gymnich committed
339
                out << llvm::left_justify(val->getName(), 6);
Tim Gymnich's avatar
Tim Gymnich committed
340
            } else {
Tim Gymnich's avatar
Tim Gymnich committed
341
                out << llvm::left_justify("<>", 6);
342
343
344
345
            }
        }
        out << "\n" << m << "\n";
    }
346
347
348
}

void AffineRelation::debug_output(Instruction const& inst, Matrix<int> operands) {
349
    for (auto m: basis) {
Tim Gymnich's avatar
Tim Gymnich committed
350
        dbgs(3) << llvm::left_justify("", 8);
351
352
        for (auto [val, idx]: index) {
            if (val->hasName()) {
Tim Gymnich's avatar
Tim Gymnich committed
353
                dbgs(3) << llvm::left_justify(val->getName(), 6);
Tim Gymnich's avatar
Tim Gymnich committed
354
            } else {
Tim Gymnich's avatar
Tim Gymnich committed
355
                dbgs(3) << llvm::left_justify("<>", 6);
356
357
358
359
            }
        }
        dbgs(3) << "\n" << m << "\n";
    }
360
361
362
}

}