 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
62.5% |
10 / 16 |
| Generated: |
2009-05-17 22:47 |
|
Branches Executed: |
75.0% |
12 / 16 |
| |
|
Line Coverage: |
81.8% |
36 / 44 |
| |
 |
|
 |
1 : //===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file was developed by the LLVM research group and is distributed under
6 : // the University of Illinois Open Source License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // Heavily modified by piotrek to get rid of the binary search transform,
11 : // as it was creating multiple paths through the program (i.e., extra paths
12 : // that didn't exist in the original program).
13 : //
14 :
15 : #include "Passes.h"
16 : #include <algorithm>
17 :
18 : using namespace llvm;
19 :
20 : namespace klee {
21 :
22 : char LowerSwitchPass::ID = 0;
23 :
24 : // The comparison function for sorting the switch case values in the vector.
25 : struct SwitchCaseCmp {
26 : bool operator () (const LowerSwitchPass::SwitchCase& C1,
27 : const LowerSwitchPass::SwitchCase& C2) {
28 :
29 : const ConstantInt* CI1 = cast<const ConstantInt>(C1.value);
30 : const ConstantInt* CI2 = cast<const ConstantInt>(C2.value);
31 : return CI1->getValue().slt(CI2->getValue());
32 : }
33 : };
34 :
35 6: bool LowerSwitchPass::runOnFunction(Function &F) {
36 6: bool changed = false;
37 :
35: branch 0 taken
6: branch 1 taken
38 41: for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
39 35: BasicBlock *cur = I++; // Advance over block so we don't traverse new blocks
40 :
1: branch 1 taken
34: branch 2 taken
41 70: if (SwitchInst *SI = dyn_cast<SwitchInst>(cur->getTerminator())) {
42 1: changed = true;
43 1: processSwitchInst(SI);
44 : }
45 : }
46 :
47 6: return changed;
48 : }
49 :
50 : // switchConvert - Convert the switch statement into a linear scan
51 : // through all the case values
52 : void LowerSwitchPass::switchConvert(CaseItr begin, CaseItr end,
53 : Value* value, BasicBlock* origBlock,
54 1: BasicBlock* defaultBlock)
55 : {
56 1: BasicBlock *curHead = defaultBlock;
57 1: Function *F = origBlock->getParent();
58 :
59 : // iterate through all the cases, creating a new BasicBlock for each
70: branch 0 taken
1: branch 1 taken
60 72: for (CaseItr it = begin; it < end; ++it) {
61 140: BasicBlock *newBlock = BasicBlock::Create("NodeBlock");
62 : Function::iterator FI = origBlock;
63 140: F->getBasicBlockList().insert(++FI, newBlock);
64 :
65 : ICmpInst *cmpInst = new ICmpInst(ICmpInst::ICMP_EQ,
66 : value,
67 : it->value,
68 280: "Case Comparison");
69 :
70 70: newBlock->getInstList().push_back(cmpInst);
71 140: BranchInst::Create(it->block, curHead, cmpInst, newBlock);
72 :
73 : // If there were any PHI nodes in this successor, rewrite one entry
74 : // from origBlock to come from newBlock.
0: branch 1 not taken
70: branch 2 taken
75 210: for (BasicBlock::iterator bi = it->block->begin(); isa<PHINode>(bi); ++bi) {
76 0: PHINode* PN = cast<PHINode>(bi);
77 :
78 0: int blockIndex = PN->getBasicBlockIndex(origBlock);
0: branch 0 not taken
0: branch 1 not taken
79 0: assert(blockIndex != -1 && "Switch didn't go to this successor??");
80 0: PN->setIncomingBlock((unsigned)blockIndex, newBlock);
81 : }
82 :
83 70: curHead = newBlock;
84 : }
85 :
86 : // Branch to our shiny new if-then stuff...
87 1: BranchInst::Create(curHead, origBlock);
88 1: }
89 :
90 : // processSwitchInst - Replace the specified switch instruction with a sequence
91 : // of chained if-then instructions.
92 : //
93 1: void LowerSwitchPass::processSwitchInst(SwitchInst *SI) {
94 2: BasicBlock *origBlock = SI->getParent();
95 1: BasicBlock *defaultBlock = SI->getDefaultDest();
96 1: Function *F = origBlock->getParent();
97 1: Value *switchValue = SI->getOperand(0);
98 :
99 : // Create a new, empty default block so that the new hierarchy of
100 : // if-then statements go to this and the PHI nodes are happy.
101 2: BasicBlock* newDefault = BasicBlock::Create("newDefault");
102 :
103 1: F->getBasicBlockList().insert(defaultBlock, newDefault);
104 1: BranchInst::Create(defaultBlock, newDefault);
105 :
106 : // If there is an entry in any PHI nodes for the default edge, make sure
107 : // to update them as well.
0: branch 1 not taken
1: branch 2 taken
108 2: for (BasicBlock::iterator I = defaultBlock->begin(); isa<PHINode>(I); ++I) {
109 0: PHINode *PN = cast<PHINode>(I);
110 0: int BlockIdx = PN->getBasicBlockIndex(origBlock);
0: branch 0 not taken
0: branch 1 not taken
111 0: assert(BlockIdx != -1 && "Switch didn't go to this successor??");
112 0: PN->setIncomingBlock((unsigned)BlockIdx, newDefault);
113 : }
114 :
115 : CaseVector cases;
70: branch 0 taken
1: branch 1 taken
116 142: for (unsigned i = 1; i < SI->getNumSuccessors(); ++i)
117 : cases.push_back(SwitchCase(SI->getSuccessorValue(i),
118 70: SI->getSuccessor(i)));
119 :
120 : // reverse cases, as switchConvert constructs a chain of
121 : // basic blocks by appending to the front. if we reverse,
122 : // the if comparisons will happen in the same order
123 : // as the cases appear in the switch
124 1: std::reverse(cases.begin(), cases.end());
125 :
126 1: switchConvert(cases.begin(), cases.end(), switchValue, origBlock, newDefault);
127 :
128 : // We are now done with the switch instruction, so delete it
129 2: origBlock->getInstList().erase(SI);
130 1: }
131 :
132 : }
Generated: 2009-05-17 22:47 by zcov