fixpoint.cpp 14.3 KB
Newer Older
Administrator's avatar
initial  
Administrator committed
1
2
3
4
5
6
7
8
9
#include "fixpoint.h"

#include <unordered_map>
#include <vector>

#include "llvm/IR/CFG.h"
#include "llvm/IR/Module.h"

#include "global.h"
Tim Gymnich's avatar
Tim Gymnich committed
10

Administrator's avatar
initial  
Administrator committed
11
12
#include "value_set.h"
#include "simple_interval.h"
Tim Gymnich's avatar
Tim Gymnich committed
13
#include "normalized_conjunction.h"
14
#include "affine_relation.h"
Tim Gymnich's avatar
Tim Gymnich committed
15
16

#include "fixpoint_widening.cpp"
Tim Gymnich's avatar
Tim Gymnich committed
17
#include "hash_utils.h"
Tim Gymnich's avatar
Tim Gymnich committed
18

19
20
#include "llvm/ADT/PostOrderIterator.h"

Administrator's avatar
initial  
Administrator committed
21
22
namespace pcpo {

Tim Gymnich's avatar
Tim Gymnich committed
23
24
25
using namespace llvm;
using namespace std;

Administrator's avatar
initial  
Administrator committed
26
27
28
29
30
31
32
static llvm::RegisterPass<AbstractInterpretationPass> Y("painpass", "AbstractInterpretation Pass");

char AbstractInterpretationPass::ID;

int debug_level = DEBUG_LEVEL; // from global.hpp


33
using Callstring = vector<Function const *>;
34
35
using NodeKey = pair<Callstring, BasicBlock const *>;

36
37
38
39
40
41
42
43
44
45
46
47
// MARK: - To String

llvm::raw_ostream& operator<<(llvm::raw_ostream& os, BasicBlock const& basic_block) {
    os << "%";
    if (llvm::Function const* f = basic_block.getParent()) {
        os << f->getName() << ".";
    }
    return os << basic_block.getName();
}

llvm::raw_ostream& operator<<(llvm::raw_ostream& os, Callstring const& callstring) {
    for (auto call : callstring) {
Tim Gymnich's avatar
Tim Gymnich committed
48
49
50
51
        os << call->getName();
        if (call != callstring.back()) {
            os << " -> ";
        }
52
53
54
55
56
57
58
59
60
    }
    return os;
}

llvm::raw_ostream& operator<<(llvm::raw_ostream& os, NodeKey const& key) {
    return os << "[" << *key.second << "," << key.first << "]";
}


Tim Gymnich's avatar
Tim Gymnich committed
61
62
template <typename AbstractState>
struct Node {
Tim Gymnich's avatar
Tim Gymnich committed
63
    BasicBlock const* basic_block;
64
    /// Function calls the lead to this basic block. The last element is always the current function.
65
    Callstring callstring;
Tim Gymnich's avatar
Tim Gymnich committed
66
67
68
    AbstractState state = {};
    bool update_scheduled = false; // Whether the node is already in the worklist

69
70
71
72
73
74
75
76
77
    /// Check wether this basic block is the entry block of its function.
    bool isEntry() const {
        return basic_block == &function()->getEntryBlock();
    }

    /// Function in which this basic block is located.
    Function const* function() const {
        return callstring.back();
    }
Tim Gymnich's avatar
Tim Gymnich committed
78
79
};

Tim Gymnich's avatar
Tim Gymnich committed
80
Callstring callstring_for(Function const* function, Callstring const& callstring, int max_length) {
81
82
    Callstring new_callstring;
    for (auto call: callstring) {
Tim Gymnich's avatar
Tim Gymnich committed
83
        if (max_length-- > 0) {
84
85
86
87
88
            new_callstring.push_back(call);
        } else {
            return new_callstring;
        }
    }
Tim Gymnich's avatar
Tim Gymnich committed
89
    new_callstring.push_back(function);
90
91
92
    return new_callstring;
}

93

Tim Gymnich's avatar
Tim Gymnich committed
94
95
96
97
template<typename AbstractState>
vector<Node<AbstractState>*> register_function(llvm::Function const* function, Callstring const& callstring, int callstack_depth, unordered_map<pcpo::NodeKey, Node<AbstractState>> &nodes) {
    Callstring new_callstring = callstring_for(function, callstring, callstack_depth);
    vector<Node<AbstractState>*> inserted_nodes;
98
99
100
101
102
103
104
105
106
107

    for (po_iterator<BasicBlock const*> I = po_begin(&function->getEntryBlock()),
         IE = po_end(&function->getEntryBlock());
         I != IE; ++I) {

        BasicBlock const* basic_block = *I;

        dbgs(1) << "  Found basic block: " << basic_block->getName() << '\n';
        NodeKey key = {new_callstring, basic_block};
        Node<AbstractState> node = {basic_block, new_callstring};
108
109
110
        if (node.isEntry()) {
            node.state = AbstractState {*node.function()};
        }
111
        inserted_nodes.push_back(&nodes[key]);
Tim Gymnich's avatar
Tim Gymnich committed
112
113
114
115
116
117
118
119
120
121
122
123
124
125
        nodes[key] = node;
    }
    return inserted_nodes;
}

template<typename AbstractState>
    void add_to_worklist(vector<Node<AbstractState>*> &nodes, vector<Node<AbstractState>*> &worklist) {
    for (Node<AbstractState>* node : nodes) {
        node->update_scheduled = true;
        worklist.push_back(node);
    }
}


126
127
128
// Run the simple fixpoint algorithm with callstrings. AbstractState should implement the interface 
// documented in AbstractStateDummy (no need to subclass or any of that, just implement the methods
// with the right signatures and take care to fulfil the contracts outlines above).
Administrator's avatar
initial  
Administrator committed
129
130
131
132
133
// Note that a lot of this code is duplicated in executeFixpointAlgorithmWidening in
// fixpoint_widening.cpp, so if you fix any bugs in here, they probably should be fixed there as
// well.
//  Tip: Look at a diff of fixpoint.cpp and fixpoint_widening.cpp with a visual diff tool (I
// recommend Meld.)
Tim Gymnich's avatar
Tim Gymnich committed
134
135
136
137
template<typename AbstractState,
    int iterations_max = 1000,
    int callstack_depth = 1,
    Merge_op::Type merge_op = Merge_op::UPPER_BOUND>
Tim Gymnich's avatar
Tim Gymnich committed
138
void executeFixpointAlgorithm(Module const& M) {
Tim Gymnich's avatar
Tim Gymnich committed
139
    using Node = Node<AbstractState>;
Administrator's avatar
initial  
Administrator committed
140
141
142
143

    // A node in the control flow graph, i.e. a basic block. Here, we need a bit of additional data
    // per node to execute the fixpoint algorithm.

144
145
    unordered_map<NodeKey, Node> nodes;
    vector<Node *> worklist;
Administrator's avatar
initial  
Administrator committed
146

147
    // We only consider the main function in the beginning. If no main exists, nothing is evaluated!
Tim Gymnich's avatar
Tim Gymnich committed
148
    Function const* main_func = M.getFunction("main");
Administrator's avatar
initial  
Administrator committed
149

150
151
    // TODO: Check what this does for release clang, probably write out a warning
    dbgs(1) << "Initialising fixpoint algorithm, collecting basic blocks\n";
Administrator's avatar
initial  
Administrator committed
152

153
    // Register basic blocks of the main function
154
155
    auto main_basic_blocks = register_function(main_func, {}, callstack_depth, nodes);
    add_to_worklist(main_basic_blocks, worklist);
156

Administrator's avatar
initial  
Administrator committed
157
158
159
160
    dbgs(1) << "\nWorklist initialised with " << worklist.size() << (worklist.size() != 1 ? " entries" : " entry")
            << ". Starting fixpoint iteration...\n";

    for (int iter = 0; !worklist.empty() and iter < iterations_max; ++iter) {
161
        Node& node = *worklist.back();
Administrator's avatar
initial  
Administrator committed
162
163
164
        worklist.pop_back();
        node.update_scheduled = false;

165
        dbgs(1) << "\nIteration " << iter << ", considering basic block "
166
167
                << *node.basic_block << " with callstring "
                << node.callstring << '\n';
Administrator's avatar
initial  
Administrator committed
168
169
170

        AbstractState state_new; // Set to bottom

171
        if (node.isEntry()) {
Administrator's avatar
initial  
Administrator committed
172
173
            dbgs(1) << "  Merging function parameters, is entry block\n";

174
            // if it is the entry node, then its state should be top
Tim Gymnich's avatar
Tim Gymnich committed
175
            state_new.merge(merge_op, node.state);
176
            state_new.isBottom = false;
Administrator's avatar
initial  
Administrator committed
177
178
        }

Tim Gymnich's avatar
Tim Gymnich committed
179
180
        dbgs(1) << "  Merge of " << pred_size(node.basic_block)
                << (pred_size(node.basic_block) != 1 ? " predecessors.\n" : " predecessor.\n");
Administrator's avatar
initial  
Administrator committed
181
182

        // Collect the predecessors
Tim Gymnich's avatar
Tim Gymnich committed
183
        vector<AbstractState> predecessors;
Tim Gymnich's avatar
Tim Gymnich committed
184
185
        for (BasicBlock const* basic_block: llvm::predecessors(node.basic_block)) {
            dbgs(3) << "    Merging basic block " << *basic_block << '\n';
Administrator's avatar
initial  
Administrator committed
186

Tim Gymnich's avatar
Tim Gymnich committed
187
188
            AbstractState state_branched {nodes[{{node.callstring}, basic_block}].state};
            state_branched.branch(*basic_block, *node.basic_block);
Tim Gymnich's avatar
Tim Gymnich committed
189
            state_new.merge(merge_op, state_branched);
Administrator's avatar
initial  
Administrator committed
190
191
192
            predecessors.push_back(state_branched);
        }

Tim Gymnich's avatar
Tim Gymnich committed
193
        dbgs(2) << "  Relevant incoming state is:\n"; state_new.printIncoming(*node.basic_block, dbgs(2), 4);
Administrator's avatar
initial  
Administrator committed
194
195
196

        // Apply the basic block
        dbgs(3) << "  Applying basic block\n";
197
198
199
200
201

        if (state_new.isBottom) {
            dbgs(3) << "    Basic block is unreachable, everything is bottom\n";
        } else {
            // Applies all instrucions of a basic block
Tim Gymnich's avatar
Tim Gymnich committed
202
            for (Instruction const& inst: *node.basic_block) {
203
204

                // Handles return instructions
Tim Gymnich's avatar
Tim Gymnich committed
205
                if (isa<ReturnInst>(&inst)) {
206
207
208
209
210
211
212
                    state_new.applyReturnInst(inst);
                }

                // If the result of the instruction is not used, there is no reason to compute
                // it. (There are no side-effects in LLVM IR. (I hope.))
                if (inst.use_empty()) {
                    // Except for call instructions, we still want to get that information
Tim Gymnich's avatar
Tim Gymnich committed
213
                    if (not isa<CallInst>(&inst)) {
Tim Gymnich's avatar
Tim Gymnich committed
214
                        dbgs(3) << "    Empty use of instruction, " << inst.getOpcodeName() << " skipping...\n";
215
216
217
218
219
                        continue;
                    }
                }

                // Handles merging points
Tim Gymnich's avatar
Tim Gymnich committed
220
                if (isa<PHINode>(&inst)) {
221

Tim Gymnich's avatar
Tim Gymnich committed
222
                    state_new.applyPHINode(*node.basic_block, predecessors, inst);
223
224

                // Handles function calls 
Tim Gymnich's avatar
Tim Gymnich committed
225
                } else if (CallInst const* call = dyn_cast<CallInst>(&inst)) {
226
227
228

                    // Checks if an input parameter for the callee is bottom. If so,
                    // then skip the calculation of the call instruction for now
229
                    if (state_new.checkOperandsForBottom(inst)) continue;
230

Tim Gymnich's avatar
Tim Gymnich committed
231
                    Function const* callee_func = call->getCalledFunction();
232
233
234
235
236
237
238

                    // Checks for functions, such as printf and skips them
                    if (callee_func->empty()) {
                        dbgs(3) << "    Function " << callee_func->getName() << " is external, skipping...\n";
                        continue;
                    }

Tim Gymnich's avatar
Tim Gymnich committed
239
                    Callstring new_callstring = callstring_for(callee_func, node.callstring, callstack_depth);
240
241

                    NodeKey callee_element = {new_callstring, &callee_func->getEntryBlock()};
242
                    vector<Node*> callee_basic_blocks;
243
244
245
246
247
248
249
250
251
                    bool changed;

                    // Checks whether a node with key [%callee entry block, %caller basic block],
                    // i.e. an entry block with callstring of caller basic block, exists.
                    // If not, all nodes with their corrosponding keys are initilized for the callee function.
                    if (nodes.find(callee_element) == nodes.end()) { 
                        // Check if abstract_state of call.bb is bottom or not
                        dbgs(3) << "    No information regarding function call %" << call->getCalledFunction()->getName() << "\n";

252
                        callee_basic_blocks = register_function(callee_func, node.callstring, callstack_depth, nodes);
253
254
255
256

                        nodes[callee_element].state = AbstractState{ callee_func, state_new, call };
                        changed = true;
                    } else {
Tim Gymnich's avatar
Tim Gymnich committed
257
                        //update callee
Tim Gymnich's avatar
Tim Gymnich committed
258
                        AbstractState before = nodes[callee_element].state;
259
260
261
262
263
264
265
266
267
268

                        // Collect all basic blocks of callee_func
                        for (po_iterator<BasicBlock const*> I = po_begin(&callee_func->getEntryBlock()),
                             IE = po_end(&callee_func->getEntryBlock());
                             I != IE; ++I) {
                            BasicBlock const* basic_block = *I;
                            NodeKey key = {new_callstring, basic_block};
                            callee_basic_blocks.push_back(&nodes[key]);
                        }

Tim Gymnich's avatar
Tim Gymnich committed
269
270
                        AbstractState state_update{ callee_func, state_new, call };
                        changed = nodes[callee_element].state.merge(merge_op, state_update);
271
272
273
                    }

                    //Getting the last block
Tim Gymnich's avatar
Tim Gymnich committed
274
                    BasicBlock const* end_block = &*prev(callee_func->end());
275
                    NodeKey end_element = {new_callstring, end_block};
276
277
278
279
280
                    state_new.applyCallInst(inst, end_block, nodes[end_element].state);

                    // If input parameters have changed, we want to interpret the function once again
                    // and reevaluate the nodes of possible callers.
                    if (changed) {
281
                        for (auto& [key, value]: nodes) {
282
                            if (key.second == node.basic_block and not value.update_scheduled) {
283
                                dbgs(3) << "      Adding possible caller " << key << " to worklist\n";
284
285
                                worklist.push_back(&value);
                                value.update_scheduled = true;
286
287
288
289
290
                            }
                        }
                        
                        // Checks if the key of the callee functions entry node is already on the worklist,
                        // this is necessary for recursions.
291
292
293
294
295
                        for (Node* elem: callee_basic_blocks) {
                            if (!elem->update_scheduled) {
                                worklist.push_back(elem);
                                elem->update_scheduled = true;

Tim Gymnich's avatar
Tim Gymnich committed
296
                                dbgs(3) << "      Adding callee " << *elem->basic_block << " " << elem->callstring << " to worklist\n";
297
298
299
                            } else {
                                dbgs(3) << "      Callee already on worklist, nothing to add...\n";
                            }
300
301
302
                        }
                    }
                } else {
303
                    if (state_new.checkOperandsForBottom(inst)) continue;
304
305
306
307
                    state_new.applyDefault(inst);
                }
            }
        }
Administrator's avatar
initial  
Administrator committed
308
309
310

        // Merge the state back into the node
        dbgs(3) << "  Merging with stored state\n";
Tim Gymnich's avatar
Tim Gymnich committed
311
        bool changed = node.state.merge(merge_op, state_new);
Administrator's avatar
initial  
Administrator committed
312

313
        dbgs(2) << "  Outgoing state " << (changed ? "changed" : "didn't change") << ":\n"; state_new.printOutgoing(*node.basic_block, dbgs(2), 4);
Administrator's avatar
initial  
Administrator committed
314
315
316
317

        // No changes, so no need to do anything else
        if (not changed) continue;

Tim Gymnich's avatar
Tim Gymnich committed
318
319
        dbgs(2) << "  State changed, notifying " << succ_size(node.basic_block)
                << (succ_size(node.basic_block) != 1 ? " successors\n" : " successor\n");
Administrator's avatar
initial  
Administrator committed
320
321

        // Something changed and we will need to update the successors
Tim Gymnich's avatar
Tim Gymnich committed
322
        for (BasicBlock const* succ_bb: successors(node.basic_block)) {
323
            NodeKey succ_key = {{node.callstring}, succ_bb};
324
            Node& succ = nodes[succ_key];
Administrator's avatar
initial  
Administrator committed
325
            if (not succ.update_scheduled) {
326
                worklist.push_back(&succ);
Administrator's avatar
initial  
Administrator committed
327
328
                succ.update_scheduled = true;

329
                dbgs(3) << "    Adding " << succ_key << " to worklist\n";
Administrator's avatar
initial  
Administrator committed
330
331
332
333
334
335
336
            }
        }
    }

    if (!worklist.empty()) {
        dbgs(0) << "Iteration terminated due to exceeding loop count.\n";
    }
337
     
Administrator's avatar
initial  
Administrator committed
338
339
    // Output the final result
    dbgs(0) << "\nFinal result:\n";
340
    for (auto const& [key, node]: nodes) {
341
        dbgs(0) << key << ":\n";
342
        node.state.printOutgoing(*node.basic_block, dbgs(0), 2);
Administrator's avatar
initial  
Administrator committed
343
    }
344

Administrator's avatar
initial  
Administrator committed
345
346
347
348
349
}

bool AbstractInterpretationPass::runOnModule(llvm::Module& M) {
    using AbstractState = AbstractStateValueSet<SimpleInterval>;

350
351
//     Use either the standard fixpoint algorithm or the version with widening
//    executeFixpointAlgorithm<AbstractState>(M);
352
353
//     executeFixpointAlgorithm<NormalizedConjunction>(M);
    executeFixpointAlgorithm<AffineRelation>(M);
Tim Gymnich's avatar
Tim Gymnich committed
354
355
//    executeFixpointAlgorithmWidening<AbstractState>(M);

Administrator's avatar
initial  
Administrator committed
356
357
358
359
360
361
362
363
    // We never change anything
    return false;
}

void AbstractInterpretationPass::getAnalysisUsage(llvm::AnalysisUsage& info) const {
    info.setPreservesAll();
}

364

Administrator's avatar
initial  
Administrator committed
365
366
} /* end of namespace pcpo */