klee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
PhiCleaner.cpp
Go to the documentation of this file.
1 //===-- PhiCleaner.cpp ----------------------------------------------------===//
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 #include "Passes.h"
11 
12 #include <set>
13 
14 using namespace llvm;
15 
17 
19  bool changed = false;
20 
21  for (Function::iterator b = f.begin(), be = f.end(); b != be; ++b) {
22  BasicBlock::iterator it = b->begin();
23 
24  if (it->getOpcode() == Instruction::PHI) {
25  PHINode *reference = cast<PHINode>(it);
26 
27  std::set<Value*> phis;
28  phis.insert(reference);
29 
30  unsigned numBlocks = reference->getNumIncomingValues();
31  for (++it; isa<PHINode>(*it); ++it) {
32  PHINode *pi = cast<PHINode>(it);
33 
34  assert(numBlocks == pi->getNumIncomingValues());
35 
36  // see if it is out of order
37  unsigned i;
38  for (i=0; i<numBlocks; i++)
39  if (pi->getIncomingBlock(i) != reference->getIncomingBlock(i))
40  break;
41 
42  if (i!=numBlocks) {
43  std::vector<Value*> values;
44  values.reserve(numBlocks);
45  for (unsigned i=0; i<numBlocks; i++)
46  values[i] = pi->getIncomingValueForBlock(reference->getIncomingBlock(i));
47  for (unsigned i=0; i<numBlocks; i++) {
48  pi->setIncomingBlock(i, reference->getIncomingBlock(i));
49  pi->setIncomingValue(i, values[i]);
50  }
51  changed = true;
52  }
53 
54  // see if it uses any previously defined phi nodes
55  for (i=0; i<numBlocks; i++) {
56  Value *value = pi->getIncomingValue(i);
57 
58  if (phis.find(value) != phis.end()) {
59  // fix by making a "move" at the end of the incoming block
60  // to a new temporary, which is thus known not to be a phi
61  // result. we could be somewhat more efficient about this
62  // by sharing temps and by reordering phi instructions so
63  // this isn't completely necessary, but in the end this is
64  // just a pathological case which does not occur very
65  // often.
66  Instruction *tmp =
67  new BitCastInst(value,
68  value->getType(),
69  value->getName() + ".phiclean",
70  pi->getIncomingBlock(i)->getTerminator());
71  pi->setIncomingValue(i, tmp);
72  }
73 
74  changed = true;
75  }
76 
77  phis.insert(pi);
78  }
79  }
80  }
81 
82  return changed;
83 }
static char ID
Definition: Passes.h:113
virtual bool runOnFunction(llvm::Function &f)
Definition: PhiCleaner.cpp:18