llvm_mode/split-compares-pass.so.cc - platform/external/AFLplusplus - Git at Google

 /*
  * Copyright 2016 laf-intel
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "llvm/Pass.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/IR/Module.h"

 #include "llvm/IR/IRBuilder.h"

 using namespace llvm;

 namespace {
   class SplitComparesTransform : public ModulePass {
     public:
       static char ID;
       SplitComparesTransform() : ModulePass(ID) {}

       bool runOnModule(Module &M) override;
 #if LLVM_VERSION_MAJOR >= 4
       StringRef getPassName() const override {
 #else
       const char * getPassName() const override {
 #endif
         return "simplifies and splits ICMP instructions";
       }
     private:
       bool splitCompares(Module &M, unsigned bitw);
       bool simplifyCompares(Module &M);
       bool simplifySignedness(Module &M);

   };
 }

 char SplitComparesTransform::ID = 0;

 /* This function splits ICMP instructions with xGE or xLE predicates into two
  * ICMP instructions with predicate xGT or xLT and EQ */
 bool SplitComparesTransform::simplifyCompares(Module &M) {
   LLVMContext &C = M.getContext();
   std::vector<Instruction*> icomps;
   IntegerType *Int1Ty = IntegerType::getInt1Ty(C);

   /* iterate over all functions, bbs and instruction and add
    * all integer comparisons with >= and <= predicates to the icomps vector */
   for (auto &F : M) {
     for (auto &BB : F) {
       for (auto &IN: BB) {
         CmpInst* selectcmpInst = nullptr;

         if ((selectcmpInst = dyn_cast<CmpInst>(&IN))) {

           if (selectcmpInst->getPredicate() != CmpInst::ICMP_UGE &&
               selectcmpInst->getPredicate() != CmpInst::ICMP_SGE &&
               selectcmpInst->getPredicate() != CmpInst::ICMP_ULE &&
               selectcmpInst->getPredicate() != CmpInst::ICMP_SLE ) {
             continue;
           }

           auto op0 = selectcmpInst->getOperand(0);
           auto op1 = selectcmpInst->getOperand(1);

           IntegerType* intTyOp0 = dyn_cast<IntegerType>(op0->getType());
           IntegerType* intTyOp1 = dyn_cast<IntegerType>(op1->getType());

           /* this is probably not needed but we do it anyway */
           if (!intTyOp0 || !intTyOp1) {
             continue;
           }

           icomps.push_back(selectcmpInst);
         }
       }
     }
   }

   if (!icomps.size()) {
     return false;
   }


   for (auto &IcmpInst: icomps) {
     BasicBlock* bb = IcmpInst->getParent();

     auto op0 = IcmpInst->getOperand(0);
     auto op1 = IcmpInst->getOperand(1);

     /* find out what the new predicate is going to be */
     auto pred = dyn_cast<CmpInst>(IcmpInst)->getPredicate();
     CmpInst::Predicate new_pred;
     switch(pred) {
       case CmpInst::ICMP_UGE:
         new_pred = CmpInst::ICMP_UGT;
         break;
       case CmpInst::ICMP_SGE:
         new_pred = CmpInst::ICMP_SGT;
         break;
       case CmpInst::ICMP_ULE:
         new_pred = CmpInst::ICMP_ULT;
         break;
       case CmpInst::ICMP_SLE:
         new_pred = CmpInst::ICMP_SLT;
         break;
       default: // keep the compiler happy
         continue;
     }

     /* split before the icmp instruction */
     BasicBlock* end_bb = bb->splitBasicBlock(BasicBlock::iterator(IcmpInst));

     /* the old bb now contains a unconditional jump to the new one (end_bb)
      * we need to delete it later */

     /* create the ICMP instruction with new_pred and add it to the old basic
      * block bb it is now at the position where the old IcmpInst was */
     Instruction* icmp_np;
     icmp_np = CmpInst::Create(Instruction::ICmp, new_pred, op0, op1);
     bb->getInstList().insert(bb->getTerminator()->getIterator(), icmp_np);

     /* create a new basic block which holds the new EQ icmp */
     Instruction *icmp_eq;
     /* insert middle_bb before end_bb */
     BasicBlock* middle_bb =  BasicBlock::Create(C, "injected",
       end_bb->getParent(), end_bb);
     icmp_eq = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, op0, op1);
     middle_bb->getInstList().push_back(icmp_eq);
     /* add an unconditional branch to the end of middle_bb with destination
      * end_bb */
     BranchInst::Create(end_bb, middle_bb);

     /* replace the uncond branch with a conditional one, which depends on the
      * new_pred icmp. True goes to end, false to the middle (injected) bb */
     auto term = bb->getTerminator();
     BranchInst::Create(end_bb, middle_bb, icmp_np, bb);
     term->eraseFromParent();


     /* replace the old IcmpInst (which is the first inst in end_bb) with a PHI
      * inst to wire up the loose ends */
     PHINode *PN = PHINode::Create(Int1Ty, 2, "");
     /* the first result depends on the outcome of icmp_eq */
     PN->addIncoming(icmp_eq, middle_bb);
     /* if the source was the original bb we know that the icmp_np yielded true
      * hence we can hardcode this value */
     PN->addIncoming(ConstantInt::get(Int1Ty, 1), bb);
     /* replace the old IcmpInst with our new and shiny PHI inst */
     BasicBlock::iterator ii(IcmpInst);
     ReplaceInstWithInst(IcmpInst->getParent()->getInstList(), ii, PN);
   }

   return true;
 }

 /* this function transforms signed compares to equivalent unsigned compares */
 bool SplitComparesTransform::simplifySignedness(Module &M) {
   LLVMContext &C = M.getContext();
   std::vector<Instruction*> icomps;
   IntegerType *Int1Ty = IntegerType::getInt1Ty(C);

   /* iterate over all functions, bbs and instruction and add
    * all signed compares to icomps vector */
   for (auto &F : M) {
     for (auto &BB : F) {
       for(auto &IN: BB) {
         CmpInst* selectcmpInst = nullptr;

         if ((selectcmpInst = dyn_cast<CmpInst>(&IN))) {

           if (selectcmpInst->getPredicate() != CmpInst::ICMP_SGT &&
              selectcmpInst->getPredicate() != CmpInst::ICMP_SLT
              ) {
             continue;
           }

           auto op0 = selectcmpInst->getOperand(0);
           auto op1 = selectcmpInst->getOperand(1);

           IntegerType* intTyOp0 = dyn_cast<IntegerType>(op0->getType());
           IntegerType* intTyOp1 = dyn_cast<IntegerType>(op1->getType());

           /* see above */
           if (!intTyOp0 || !intTyOp1) {
             continue;
           }

           /* i think this is not possible but to lazy to look it up */
           if (intTyOp0->getBitWidth() != intTyOp1->getBitWidth()) {
             continue;
           }

           icomps.push_back(selectcmpInst);
         }
       }
     }
   }

   if (!icomps.size()) {
     return false;
   }

   for (auto &IcmpInst: icomps) {
     BasicBlock* bb = IcmpInst->getParent();

     auto op0 = IcmpInst->getOperand(0);
     auto op1 = IcmpInst->getOperand(1);

     IntegerType* intTyOp0 = dyn_cast<IntegerType>(op0->getType());
     unsigned bitw = intTyOp0->getBitWidth();
     IntegerType *IntType = IntegerType::get(C, bitw);


     /* get the new predicate */
     auto pred = dyn_cast<CmpInst>(IcmpInst)->getPredicate();
     CmpInst::Predicate new_pred;
     if (pred == CmpInst::ICMP_SGT) {
       new_pred = CmpInst::ICMP_UGT;
     } else {
       new_pred = CmpInst::ICMP_ULT;
     }

     BasicBlock* end_bb = bb->splitBasicBlock(BasicBlock::iterator(IcmpInst));

     /* create a 1 bit compare for the sign bit. to do this shift and trunc
      * the original operands so only the first bit remains.*/
     Instruction *s_op0, *t_op0, *s_op1, *t_op1, *icmp_sign_bit;

     s_op0 = BinaryOperator::Create(Instruction::LShr, op0, ConstantInt::get(IntType, bitw - 1));
     bb->getInstList().insert(bb->getTerminator()->getIterator(), s_op0);
     t_op0 = new TruncInst(s_op0, Int1Ty);
     bb->getInstList().insert(bb->getTerminator()->getIterator(), t_op0);

     s_op1 = BinaryOperator::Create(Instruction::LShr, op1, ConstantInt::get(IntType, bitw - 1));
     bb->getInstList().insert(bb->getTerminator()->getIterator(), s_op1);
     t_op1 = new TruncInst(s_op1, Int1Ty);
     bb->getInstList().insert(bb->getTerminator()->getIterator(), t_op1);

     /* compare of the sign bits */
     icmp_sign_bit = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, t_op0, t_op1);
     bb->getInstList().insert(bb->getTerminator()->getIterator(), icmp_sign_bit);

     /* create a new basic block which is executed if the signedness bit is
      * different */
     Instruction *icmp_inv_sig_cmp;
     BasicBlock* sign_bb = BasicBlock::Create(C, "sign", end_bb->getParent(), end_bb);
     if (pred == CmpInst::ICMP_SGT) {
       /* if we check for > and the op0 positive and op1 negative then the final
        * result is true. if op0 negative and op1 pos, the cmp must result
        * in false
        */
       icmp_inv_sig_cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULT, t_op0, t_op1);
     } else {
       /* just the inverse of the above statement */
       icmp_inv_sig_cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_UGT, t_op0, t_op1);
     }
     sign_bb->getInstList().push_back(icmp_inv_sig_cmp);
     BranchInst::Create(end_bb, sign_bb);

     /* create a new bb which is executed if signedness is equal */
     Instruction *icmp_usign_cmp;
     BasicBlock* middle_bb =  BasicBlock::Create(C, "injected", end_bb->getParent(), end_bb);
     /* we can do a normal unsigned compare now */
     icmp_usign_cmp = CmpInst::Create(Instruction::ICmp, new_pred, op0, op1);
     middle_bb->getInstList().push_back(icmp_usign_cmp);
     BranchInst::Create(end_bb, middle_bb);

     auto term = bb->getTerminator();
     /* if the sign is eq do a normal unsigned cmp, else we have to check the
      * signedness bit */
     BranchInst::Create(middle_bb, sign_bb, icmp_sign_bit, bb);
     term->eraseFromParent();


     PHINode *PN = PHINode::Create(Int1Ty, 2, "");

     PN->addIncoming(icmp_usign_cmp, middle_bb);
     PN->addIncoming(icmp_inv_sig_cmp, sign_bb);

     BasicBlock::iterator ii(IcmpInst);
     ReplaceInstWithInst(IcmpInst->getParent()->getInstList(), ii, PN);
   }

   return true;
 }

 /* splits icmps of size bitw into two nested icmps with bitw/2 size each */
 bool SplitComparesTransform::splitCompares(Module &M, unsigned bitw) {
   LLVMContext &C = M.getContext();

   IntegerType *Int1Ty = IntegerType::getInt1Ty(C);
   IntegerType *OldIntType = IntegerType::get(C, bitw);
   IntegerType *NewIntType = IntegerType::get(C, bitw / 2);

   std::vector<Instruction*> icomps;

   if (bitw % 2) {
     return false;
   }

   /* not supported yet */
   if (bitw > 64) {
     return false;
   }

   /* get all EQ, NE, UGT, and ULT icmps of width bitw. if the other two
    * unctions were executed only these four predicates should exist */
   for (auto &F : M) {
     for (auto &BB : F) {
       for(auto &IN: BB) {
         CmpInst* selectcmpInst = nullptr;

         if ((selectcmpInst = dyn_cast<CmpInst>(&IN))) {

           if(selectcmpInst->getPredicate() != CmpInst::ICMP_EQ &&
              selectcmpInst->getPredicate() != CmpInst::ICMP_NE &&
              selectcmpInst->getPredicate() != CmpInst::ICMP_UGT &&
              selectcmpInst->getPredicate() != CmpInst::ICMP_ULT
              ) {
             continue;
           }

           auto op0 = selectcmpInst->getOperand(0);
           auto op1 = selectcmpInst->getOperand(1);

           IntegerType* intTyOp0 = dyn_cast<IntegerType>(op0->getType());
           IntegerType* intTyOp1 = dyn_cast<IntegerType>(op1->getType());

           if (!intTyOp0 || !intTyOp1) {
             continue;
           }

           /* check if the bitwidths are the one we are looking for */
           if (intTyOp0->getBitWidth() != bitw || intTyOp1->getBitWidth() != bitw) {
             continue;
           }

           icomps.push_back(selectcmpInst);
         }
       }
     }
   }

   if (!icomps.size()) {
     return false;
   }

   for (auto &IcmpInst: icomps) {
     BasicBlock* bb = IcmpInst->getParent();

     auto op0 = IcmpInst->getOperand(0);
     auto op1 = IcmpInst->getOperand(1);

     auto pred = dyn_cast<CmpInst>(IcmpInst)->getPredicate();

     BasicBlock* end_bb = bb->splitBasicBlock(BasicBlock::iterator(IcmpInst));

     /* create the comparison of the top halves of the original operands */
     Instruction *s_op0, *op0_high, *s_op1, *op1_high, *icmp_high;

     s_op0 = BinaryOperator::Create(Instruction::LShr, op0, ConstantInt::get(OldIntType, bitw / 2));
     bb->getInstList().insert(bb->getTerminator()->getIterator(), s_op0);
     op0_high = new TruncInst(s_op0, NewIntType);
     bb->getInstList().insert(bb->getTerminator()->getIterator(), op0_high);

     s_op1 = BinaryOperator::Create(Instruction::LShr, op1, ConstantInt::get(OldIntType, bitw / 2));
     bb->getInstList().insert(bb->getTerminator()->getIterator(), s_op1);
     op1_high = new TruncInst(s_op1, NewIntType);
     bb->getInstList().insert(bb->getTerminator()->getIterator(), op1_high);

     icmp_high = CmpInst::Create(Instruction::ICmp, pred, op0_high, op1_high);
     bb->getInstList().insert(bb->getTerminator()->getIterator(), icmp_high);

     /* now we have to destinguish between == != and > < */
     if (pred == CmpInst::ICMP_EQ || pred == CmpInst::ICMP_NE) {
       /* transformation for == and != icmps */

       /* create a compare for the lower half of the original operands */
       Instruction *op0_low, *op1_low, *icmp_low;
       BasicBlock* cmp_low_bb = BasicBlock::Create(C, "injected", end_bb->getParent(), end_bb);

       op0_low = new TruncInst(op0, NewIntType);
       cmp_low_bb->getInstList().push_back(op0_low);

       op1_low = new TruncInst(op1, NewIntType);
       cmp_low_bb->getInstList().push_back(op1_low);

       icmp_low = CmpInst::Create(Instruction::ICmp, pred, op0_low, op1_low);
       cmp_low_bb->getInstList().push_back(icmp_low);
       BranchInst::Create(end_bb, cmp_low_bb);

       /* dependent on the cmp of the high parts go to the end or go on with
        * the comparison */
       auto term = bb->getTerminator();
       if (pred == CmpInst::ICMP_EQ) {
         BranchInst::Create(cmp_low_bb, end_bb, icmp_high, bb);
       } else {
         /* CmpInst::ICMP_NE */
         BranchInst::Create(end_bb, cmp_low_bb, icmp_high, bb);
       }
       term->eraseFromParent();

       /* create the PHI and connect the edges accordingly */
       PHINode *PN = PHINode::Create(Int1Ty, 2, "");
       PN->addIncoming(icmp_low, cmp_low_bb);
       if (pred == CmpInst::ICMP_EQ) {
         PN->addIncoming(ConstantInt::get(Int1Ty, 0), bb);
       } else {
         /* CmpInst::ICMP_NE */
         PN->addIncoming(ConstantInt::get(Int1Ty, 1), bb);
       }

       /* replace the old icmp with the new PHI */
       BasicBlock::iterator ii(IcmpInst);
       ReplaceInstWithInst(IcmpInst->getParent()->getInstList(), ii, PN);

     } else {
       /* CmpInst::ICMP_UGT and CmpInst::ICMP_ULT */
       /* transformations for < and > */

       /* create a basic block which checks for the inverse predicate.
        * if this is true we can go to the end if not we have to got to the
        * bb which checks the lower half of the operands */
       Instruction *icmp_inv_cmp, *op0_low, *op1_low, *icmp_low;
       BasicBlock* inv_cmp_bb = BasicBlock::Create(C, "inv_cmp", end_bb->getParent(), end_bb);
       if (pred == CmpInst::ICMP_UGT) {
         icmp_inv_cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULT, op0_high, op1_high);
       } else {
         icmp_inv_cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_UGT, op0_high, op1_high);
       }
       inv_cmp_bb->getInstList().push_back(icmp_inv_cmp);

       auto term = bb->getTerminator();
       term->eraseFromParent();
       BranchInst::Create(end_bb, inv_cmp_bb, icmp_high, bb);

       /* create a bb which handles the cmp of the lower halves */
       BasicBlock* cmp_low_bb = BasicBlock::Create(C, "injected", end_bb->getParent(), end_bb);
       op0_low = new TruncInst(op0, NewIntType);
       cmp_low_bb->getInstList().push_back(op0_low);
       op1_low = new TruncInst(op1, NewIntType);
       cmp_low_bb->getInstList().push_back(op1_low);

       icmp_low = CmpInst::Create(Instruction::ICmp, pred, op0_low, op1_low);
       cmp_low_bb->getInstList().push_back(icmp_low);
       BranchInst::Create(end_bb, cmp_low_bb);

       BranchInst::Create(end_bb, cmp_low_bb, icmp_inv_cmp, inv_cmp_bb);

       PHINode *PN = PHINode::Create(Int1Ty, 3);
       PN->addIncoming(icmp_low, cmp_low_bb);
       PN->addIncoming(ConstantInt::get(Int1Ty, 1), bb);
       PN->addIncoming(ConstantInt::get(Int1Ty, 0), inv_cmp_bb);

       BasicBlock::iterator ii(IcmpInst);
       ReplaceInstWithInst(IcmpInst->getParent()->getInstList(), ii, PN);
     }
   }
   return  true;
 }

 bool SplitComparesTransform::runOnModule(Module &M) {
   int bitw = 64;

   char* bitw_env = getenv("LAF_SPLIT_COMPARES_BITW");
   if (!bitw_env)
     bitw_env = getenv("AFL_LLVM_LAF_SPLIT_COMPARES_BITW");
   if (bitw_env) {
     bitw = atoi(bitw_env);
   }

   simplifyCompares(M);

   simplifySignedness(M);

   if (getenv("AFL_QUIET") == NULL)
     errs() << "Split-compare-pass by laf.intel@gmail.com\n";

   switch (bitw) {
     case 64:
       errs() << "Running split-compare-pass " << 64 << "\n";
       splitCompares(M, 64);

       [[clang::fallthrough]];
       /* fallthrough */
     case 32:
       errs() << "Running split-compare-pass " << 32 << "\n";
       splitCompares(M, 32);

       [[clang::fallthrough]];
       /* fallthrough */
     case 16:
       errs() << "Running split-compare-pass " << 16 << "\n";
       splitCompares(M, 16);
       break;

     default:
       errs() << "NOT Running split-compare-pass \n";
       return false;
       break;
   }

   verifyModule(M);
   return true;
 }

 static void registerSplitComparesPass(const PassManagerBuilder &,
                          legacy::PassManagerBase &PM) {
   PM.add(new SplitComparesTransform());
 }

 static RegisterStandardPasses RegisterSplitComparesPass(
     PassManagerBuilder::EP_OptimizerLast, registerSplitComparesPass);

 static RegisterStandardPasses RegisterSplitComparesTransPass0(
     PassManagerBuilder::EP_EnabledOnOptLevel0, registerSplitComparesPass);
	/*
	* Copyright 2016 laf-intel
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "llvm/Pass.h"
	#include "llvm/Support/raw_ostream.h"
	#include "llvm/IR/LegacyPassManager.h"
	#include "llvm/Transforms/IPO/PassManagerBuilder.h"
	#include "llvm/Transforms/Utils/BasicBlockUtils.h"
	#include "llvm/IR/Verifier.h"
	#include "llvm/IR/Module.h"

	#include "llvm/IR/IRBuilder.h"

	using namespace llvm;

	namespace {
	class SplitComparesTransform : public ModulePass {
	public:
	static char ID;
	SplitComparesTransform() : ModulePass(ID) {}

	bool runOnModule(Module &M) override;
	#if LLVM_VERSION_MAJOR >= 4
	StringRef getPassName() const override {
	#else
	const char * getPassName() const override {
	#endif
	return "simplifies and splits ICMP instructions";
	}
	private:
	bool splitCompares(Module &M, unsigned bitw);
	bool simplifyCompares(Module &M);
	bool simplifySignedness(Module &M);

	};
	}

	char SplitComparesTransform::ID = 0;

	/* This function splits ICMP instructions with xGE or xLE predicates into two
	* ICMP instructions with predicate xGT or xLT and EQ */
	bool SplitComparesTransform::simplifyCompares(Module &M) {
	LLVMContext &C = M.getContext();
	std::vector<Instruction*> icomps;
	IntegerType *Int1Ty = IntegerType::getInt1Ty(C);

	/* iterate over all functions, bbs and instruction and add
	* all integer comparisons with >= and <= predicates to the icomps vector */
	for (auto &F : M) {
	for (auto &BB : F) {
	for (auto &IN: BB) {
	CmpInst* selectcmpInst = nullptr;

	if ((selectcmpInst = dyn_cast<CmpInst>(&IN))) {

	if (selectcmpInst->getPredicate() != CmpInst::ICMP_UGE &&
	selectcmpInst->getPredicate() != CmpInst::ICMP_SGE &&
	selectcmpInst->getPredicate() != CmpInst::ICMP_ULE &&
	selectcmpInst->getPredicate() != CmpInst::ICMP_SLE ) {
	continue;
	}

	auto op0 = selectcmpInst->getOperand(0);
	auto op1 = selectcmpInst->getOperand(1);

	IntegerType* intTyOp0 = dyn_cast<IntegerType>(op0->getType());
	IntegerType* intTyOp1 = dyn_cast<IntegerType>(op1->getType());

	/* this is probably not needed but we do it anyway */
	if (!intTyOp0 \|\| !intTyOp1) {
	continue;
	}

	icomps.push_back(selectcmpInst);
	}
	}
	}
	}

	if (!icomps.size()) {
	return false;
	}


	for (auto &IcmpInst: icomps) {
	BasicBlock* bb = IcmpInst->getParent();

	auto op0 = IcmpInst->getOperand(0);
	auto op1 = IcmpInst->getOperand(1);

	/* find out what the new predicate is going to be */
	auto pred = dyn_cast<CmpInst>(IcmpInst)->getPredicate();
	CmpInst::Predicate new_pred;
	switch(pred) {
	case CmpInst::ICMP_UGE:
	new_pred = CmpInst::ICMP_UGT;
	break;
	case CmpInst::ICMP_SGE:
	new_pred = CmpInst::ICMP_SGT;
	break;
	case CmpInst::ICMP_ULE:
	new_pred = CmpInst::ICMP_ULT;
	break;
	case CmpInst::ICMP_SLE:
	new_pred = CmpInst::ICMP_SLT;
	break;
	default: // keep the compiler happy
	continue;
	}

	/* split before the icmp instruction */
	BasicBlock* end_bb = bb->splitBasicBlock(BasicBlock::iterator(IcmpInst));

	/* the old bb now contains a unconditional jump to the new one (end_bb)
	* we need to delete it later */

	/* create the ICMP instruction with new_pred and add it to the old basic
	* block bb it is now at the position where the old IcmpInst was */
	Instruction* icmp_np;
	icmp_np = CmpInst::Create(Instruction::ICmp, new_pred, op0, op1);
	bb->getInstList().insert(bb->getTerminator()->getIterator(), icmp_np);

	/* create a new basic block which holds the new EQ icmp */
	Instruction *icmp_eq;
	/* insert middle_bb before end_bb */
	BasicBlock* middle_bb = BasicBlock::Create(C, "injected",
	end_bb->getParent(), end_bb);
	icmp_eq = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, op0, op1);
	middle_bb->getInstList().push_back(icmp_eq);
	/* add an unconditional branch to the end of middle_bb with destination
	* end_bb */
	BranchInst::Create(end_bb, middle_bb);

	/* replace the uncond branch with a conditional one, which depends on the
	* new_pred icmp. True goes to end, false to the middle (injected) bb */
	auto term = bb->getTerminator();
	BranchInst::Create(end_bb, middle_bb, icmp_np, bb);
	term->eraseFromParent();


	/* replace the old IcmpInst (which is the first inst in end_bb) with a PHI
	* inst to wire up the loose ends */
	PHINode *PN = PHINode::Create(Int1Ty, 2, "");
	/* the first result depends on the outcome of icmp_eq */
	PN->addIncoming(icmp_eq, middle_bb);
	/* if the source was the original bb we know that the icmp_np yielded true
	* hence we can hardcode this value */
	PN->addIncoming(ConstantInt::get(Int1Ty, 1), bb);
	/* replace the old IcmpInst with our new and shiny PHI inst */
	BasicBlock::iterator ii(IcmpInst);
	ReplaceInstWithInst(IcmpInst->getParent()->getInstList(), ii, PN);
	}

	return true;
	}

	/* this function transforms signed compares to equivalent unsigned compares */
	bool SplitComparesTransform::simplifySignedness(Module &M) {
	LLVMContext &C = M.getContext();
	std::vector<Instruction*> icomps;
	IntegerType *Int1Ty = IntegerType::getInt1Ty(C);

	/* iterate over all functions, bbs and instruction and add
	* all signed compares to icomps vector */
	for (auto &F : M) {
	for (auto &BB : F) {
	for(auto &IN: BB) {
	CmpInst* selectcmpInst = nullptr;

	if ((selectcmpInst = dyn_cast<CmpInst>(&IN))) {

	if (selectcmpInst->getPredicate() != CmpInst::ICMP_SGT &&
	selectcmpInst->getPredicate() != CmpInst::ICMP_SLT
	) {
	continue;
	}

	auto op0 = selectcmpInst->getOperand(0);
	auto op1 = selectcmpInst->getOperand(1);

	IntegerType* intTyOp0 = dyn_cast<IntegerType>(op0->getType());
	IntegerType* intTyOp1 = dyn_cast<IntegerType>(op1->getType());

	/* see above */
	if (!intTyOp0 \|\| !intTyOp1) {
	continue;
	}

	/* i think this is not possible but to lazy to look it up */
	if (intTyOp0->getBitWidth() != intTyOp1->getBitWidth()) {
	continue;
	}

	icomps.push_back(selectcmpInst);
	}
	}
	}
	}

	if (!icomps.size()) {
	return false;
	}

	for (auto &IcmpInst: icomps) {
	BasicBlock* bb = IcmpInst->getParent();

	auto op0 = IcmpInst->getOperand(0);
	auto op1 = IcmpInst->getOperand(1);

	IntegerType* intTyOp0 = dyn_cast<IntegerType>(op0->getType());
	unsigned bitw = intTyOp0->getBitWidth();
	IntegerType *IntType = IntegerType::get(C, bitw);


	/* get the new predicate */
	auto pred = dyn_cast<CmpInst>(IcmpInst)->getPredicate();
	CmpInst::Predicate new_pred;
	if (pred == CmpInst::ICMP_SGT) {
	new_pred = CmpInst::ICMP_UGT;
	} else {
	new_pred = CmpInst::ICMP_ULT;
	}

	BasicBlock* end_bb = bb->splitBasicBlock(BasicBlock::iterator(IcmpInst));

	/* create a 1 bit compare for the sign bit. to do this shift and trunc
	* the original operands so only the first bit remains.*/
	Instruction s_op0, t_op0, s_op1, t_op1, *icmp_sign_bit;

	s_op0 = BinaryOperator::Create(Instruction::LShr, op0, ConstantInt::get(IntType, bitw - 1));
	bb->getInstList().insert(bb->getTerminator()->getIterator(), s_op0);
	t_op0 = new TruncInst(s_op0, Int1Ty);
	bb->getInstList().insert(bb->getTerminator()->getIterator(), t_op0);

	s_op1 = BinaryOperator::Create(Instruction::LShr, op1, ConstantInt::get(IntType, bitw - 1));
	bb->getInstList().insert(bb->getTerminator()->getIterator(), s_op1);
	t_op1 = new TruncInst(s_op1, Int1Ty);
	bb->getInstList().insert(bb->getTerminator()->getIterator(), t_op1);

	/* compare of the sign bits */
	icmp_sign_bit = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, t_op0, t_op1);
	bb->getInstList().insert(bb->getTerminator()->getIterator(), icmp_sign_bit);

	/* create a new basic block which is executed if the signedness bit is
	* different */
	Instruction *icmp_inv_sig_cmp;
	BasicBlock* sign_bb = BasicBlock::Create(C, "sign", end_bb->getParent(), end_bb);
	if (pred == CmpInst::ICMP_SGT) {
	/* if we check for > and the op0 positive and op1 negative then the final
	* result is true. if op0 negative and op1 pos, the cmp must result
	* in false
	*/
	icmp_inv_sig_cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULT, t_op0, t_op1);
	} else {
	/* just the inverse of the above statement */
	icmp_inv_sig_cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_UGT, t_op0, t_op1);
	}
	sign_bb->getInstList().push_back(icmp_inv_sig_cmp);
	BranchInst::Create(end_bb, sign_bb);

	/* create a new bb which is executed if signedness is equal */
	Instruction *icmp_usign_cmp;
	BasicBlock* middle_bb = BasicBlock::Create(C, "injected", end_bb->getParent(), end_bb);
	/* we can do a normal unsigned compare now */
	icmp_usign_cmp = CmpInst::Create(Instruction::ICmp, new_pred, op0, op1);
	middle_bb->getInstList().push_back(icmp_usign_cmp);
	BranchInst::Create(end_bb, middle_bb);

	auto term = bb->getTerminator();
	/* if the sign is eq do a normal unsigned cmp, else we have to check the
	* signedness bit */
	BranchInst::Create(middle_bb, sign_bb, icmp_sign_bit, bb);
	term->eraseFromParent();


	PHINode *PN = PHINode::Create(Int1Ty, 2, "");

	PN->addIncoming(icmp_usign_cmp, middle_bb);
	PN->addIncoming(icmp_inv_sig_cmp, sign_bb);

	BasicBlock::iterator ii(IcmpInst);
	ReplaceInstWithInst(IcmpInst->getParent()->getInstList(), ii, PN);
	}

	return true;
	}

	/* splits icmps of size bitw into two nested icmps with bitw/2 size each */
	bool SplitComparesTransform::splitCompares(Module &M, unsigned bitw) {
	LLVMContext &C = M.getContext();

	IntegerType *Int1Ty = IntegerType::getInt1Ty(C);
	IntegerType *OldIntType = IntegerType::get(C, bitw);
	IntegerType *NewIntType = IntegerType::get(C, bitw / 2);

	std::vector<Instruction*> icomps;

	if (bitw % 2) {
	return false;
	}

	/* not supported yet */
	if (bitw > 64) {
	return false;
	}

	/* get all EQ, NE, UGT, and ULT icmps of width bitw. if the other two
	* unctions were executed only these four predicates should exist */
	for (auto &F : M) {
	for (auto &BB : F) {
	for(auto &IN: BB) {
	CmpInst* selectcmpInst = nullptr;

	if ((selectcmpInst = dyn_cast<CmpInst>(&IN))) {

	if(selectcmpInst->getPredicate() != CmpInst::ICMP_EQ &&
	selectcmpInst->getPredicate() != CmpInst::ICMP_NE &&
	selectcmpInst->getPredicate() != CmpInst::ICMP_UGT &&
	selectcmpInst->getPredicate() != CmpInst::ICMP_ULT
	) {
	continue;
	}

	auto op0 = selectcmpInst->getOperand(0);
	auto op1 = selectcmpInst->getOperand(1);

	IntegerType* intTyOp0 = dyn_cast<IntegerType>(op0->getType());
	IntegerType* intTyOp1 = dyn_cast<IntegerType>(op1->getType());

	if (!intTyOp0 \|\| !intTyOp1) {
	continue;
	}

	/* check if the bitwidths are the one we are looking for */
	if (intTyOp0->getBitWidth() != bitw \|\| intTyOp1->getBitWidth() != bitw) {
	continue;
	}

	icomps.push_back(selectcmpInst);
	}
	}
	}
	}

	if (!icomps.size()) {
	return false;
	}

	for (auto &IcmpInst: icomps) {
	BasicBlock* bb = IcmpInst->getParent();

	auto op0 = IcmpInst->getOperand(0);
	auto op1 = IcmpInst->getOperand(1);

	auto pred = dyn_cast<CmpInst>(IcmpInst)->getPredicate();

	BasicBlock* end_bb = bb->splitBasicBlock(BasicBlock::iterator(IcmpInst));

	/* create the comparison of the top halves of the original operands */
	Instruction s_op0, op0_high, s_op1, op1_high, *icmp_high;

	s_op0 = BinaryOperator::Create(Instruction::LShr, op0, ConstantInt::get(OldIntType, bitw / 2));
	bb->getInstList().insert(bb->getTerminator()->getIterator(), s_op0);
	op0_high = new TruncInst(s_op0, NewIntType);
	bb->getInstList().insert(bb->getTerminator()->getIterator(), op0_high);

	s_op1 = BinaryOperator::Create(Instruction::LShr, op1, ConstantInt::get(OldIntType, bitw / 2));
	bb->getInstList().insert(bb->getTerminator()->getIterator(), s_op1);
	op1_high = new TruncInst(s_op1, NewIntType);
	bb->getInstList().insert(bb->getTerminator()->getIterator(), op1_high);

	icmp_high = CmpInst::Create(Instruction::ICmp, pred, op0_high, op1_high);
	bb->getInstList().insert(bb->getTerminator()->getIterator(), icmp_high);

	/* now we have to destinguish between == != and > < */
	if (pred == CmpInst::ICMP_EQ \|\| pred == CmpInst::ICMP_NE) {
	/* transformation for == and != icmps */

	/* create a compare for the lower half of the original operands */
	Instruction op0_low, op1_low, *icmp_low;
	BasicBlock* cmp_low_bb = BasicBlock::Create(C, "injected", end_bb->getParent(), end_bb);

	op0_low = new TruncInst(op0, NewIntType);
	cmp_low_bb->getInstList().push_back(op0_low);

	op1_low = new TruncInst(op1, NewIntType);
	cmp_low_bb->getInstList().push_back(op1_low);

	icmp_low = CmpInst::Create(Instruction::ICmp, pred, op0_low, op1_low);
	cmp_low_bb->getInstList().push_back(icmp_low);
	BranchInst::Create(end_bb, cmp_low_bb);

	/* dependent on the cmp of the high parts go to the end or go on with
	* the comparison */
	auto term = bb->getTerminator();
	if (pred == CmpInst::ICMP_EQ) {
	BranchInst::Create(cmp_low_bb, end_bb, icmp_high, bb);
	} else {
	/* CmpInst::ICMP_NE */
	BranchInst::Create(end_bb, cmp_low_bb, icmp_high, bb);
	}
	term->eraseFromParent();

	/* create the PHI and connect the edges accordingly */
	PHINode *PN = PHINode::Create(Int1Ty, 2, "");
	PN->addIncoming(icmp_low, cmp_low_bb);
	if (pred == CmpInst::ICMP_EQ) {
	PN->addIncoming(ConstantInt::get(Int1Ty, 0), bb);
	} else {
	/* CmpInst::ICMP_NE */
	PN->addIncoming(ConstantInt::get(Int1Ty, 1), bb);
	}

	/* replace the old icmp with the new PHI */
	BasicBlock::iterator ii(IcmpInst);
	ReplaceInstWithInst(IcmpInst->getParent()->getInstList(), ii, PN);

	} else {
	/* CmpInst::ICMP_UGT and CmpInst::ICMP_ULT */
	/* transformations for < and > */

	/* create a basic block which checks for the inverse predicate.
	* if this is true we can go to the end if not we have to got to the
	* bb which checks the lower half of the operands */
	Instruction icmp_inv_cmp, op0_low, op1_low, icmp_low;
	BasicBlock* inv_cmp_bb = BasicBlock::Create(C, "inv_cmp", end_bb->getParent(), end_bb);
	if (pred == CmpInst::ICMP_UGT) {
	icmp_inv_cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULT, op0_high, op1_high);
	} else {
	icmp_inv_cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_UGT, op0_high, op1_high);
	}
	inv_cmp_bb->getInstList().push_back(icmp_inv_cmp);

	auto term = bb->getTerminator();
	term->eraseFromParent();
	BranchInst::Create(end_bb, inv_cmp_bb, icmp_high, bb);

	/* create a bb which handles the cmp of the lower halves */
	BasicBlock* cmp_low_bb = BasicBlock::Create(C, "injected", end_bb->getParent(), end_bb);
	op0_low = new TruncInst(op0, NewIntType);
	cmp_low_bb->getInstList().push_back(op0_low);
	op1_low = new TruncInst(op1, NewIntType);
	cmp_low_bb->getInstList().push_back(op1_low);

	icmp_low = CmpInst::Create(Instruction::ICmp, pred, op0_low, op1_low);
	cmp_low_bb->getInstList().push_back(icmp_low);
	BranchInst::Create(end_bb, cmp_low_bb);

	BranchInst::Create(end_bb, cmp_low_bb, icmp_inv_cmp, inv_cmp_bb);

	PHINode *PN = PHINode::Create(Int1Ty, 3);
	PN->addIncoming(icmp_low, cmp_low_bb);
	PN->addIncoming(ConstantInt::get(Int1Ty, 1), bb);
	PN->addIncoming(ConstantInt::get(Int1Ty, 0), inv_cmp_bb);

	BasicBlock::iterator ii(IcmpInst);
	ReplaceInstWithInst(IcmpInst->getParent()->getInstList(), ii, PN);
	}
	}
	return true;
	}

	bool SplitComparesTransform::runOnModule(Module &M) {
	int bitw = 64;

	char* bitw_env = getenv("LAF_SPLIT_COMPARES_BITW");
	if (!bitw_env)
	bitw_env = getenv("AFL_LLVM_LAF_SPLIT_COMPARES_BITW");
	if (bitw_env) {
	bitw = atoi(bitw_env);
	}

	simplifyCompares(M);

	simplifySignedness(M);

	if (getenv("AFL_QUIET") == NULL)
	errs() << "Split-compare-pass by laf.intel@gmail.com\n";

	switch (bitw) {
	case 64:
	errs() << "Running split-compare-pass " << 64 << "\n";
	splitCompares(M, 64);

	[[clang::fallthrough]];
	/* fallthrough */
	case 32:
	errs() << "Running split-compare-pass " << 32 << "\n";
	splitCompares(M, 32);

	[[clang::fallthrough]];
	/* fallthrough */
	case 16:
	errs() << "Running split-compare-pass " << 16 << "\n";
	splitCompares(M, 16);
	break;

	default:
	errs() << "NOT Running split-compare-pass \n";
	return false;
	break;
	}

	verifyModule(M);
	return true;
	}

	static void registerSplitComparesPass(const PassManagerBuilder &,
	legacy::PassManagerBase &PM) {
	PM.add(new SplitComparesTransform());
	}

	static RegisterStandardPasses RegisterSplitComparesPass(
	PassManagerBuilder::EP_OptimizerLast, registerSplitComparesPass);

	static RegisterStandardPasses RegisterSplitComparesTransPass0(
	PassManagerBuilder::EP_EnabledOnOptLevel0, registerSplitComparesPass);