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