lib/LowerPrivatePointerPHIPass.cpp - external/github.com/google/clspv - Git at Google

 // Copyright 2023 The Clspv Authors. All rights reserved.
 //
 // 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 "LowerPrivatePointerPHIPass.h"
 #include "BitcastUtils.h"
 #include "Types.h"
 #include "clspv/AddressSpace.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/IR/Instructions.h"

 #define DEBUG_TYPE "LowerPrivatePointerPHI"

 namespace {

 using PartitionCallback = std::function<void(Instruction *)>;

 /// Partition the @p Instructions based on their liveness.
 void partitionInstructions(ArrayRef<WeakTrackingVH> Instructions,
                            PartitionCallback OnDead,
                            PartitionCallback OnAlive) {
   for (auto OldValueHandle : Instructions) {
     // Handle situations when the weak handle is no longer valid.
     if (!OldValueHandle.pointsToAliveValue()) {
       continue; // Nothing else to do for this handle.
     }

     auto *OldInstruction = cast<Instruction>(OldValueHandle);
     bool Dead = OldInstruction->use_empty();
     if (Dead) {
       OnDead(OldInstruction);
     } else {
       OnAlive(OldInstruction);
     }
   }
 }

 Value *getOffsetValue(IRBuilder<> &B, Type *intTy, int64_t CstVal,
                       Value *DynVal) {
   if (DynVal == nullptr) {
     return ConstantInt::get(intTy, CstVal);
   } else if (CstVal != 0) {
     return B.CreateAdd(ConstantInt::get(intTy, CstVal), DynVal);
   }
   return DynVal;
 }

 void replacePHIIncomingValue(PHINode *phi, PHINode *new_phi, Instruction *Src,
                              int64_t CstVal, Value *DynVal) {
   IRBuilder<> B(Src);
   Value *DynValOffset = getOffsetValue(B, new_phi->getType(), CstVal, DynVal);
   BasicBlock *BB = nullptr;
   for (auto &incoming : phi->incoming_values()) {
     if (incoming == Src) {
       BB = phi->getIncomingBlock(incoming);
       break;
     }
   }
   assert(BB);
   new_phi->addIncoming(DynValOffset, BB);
   phi->removeIncomingValue(BB, false);
 }

 Value *makeNewGEP(const DataLayout &DL, IRBuilder<> &B, Instruction *Src,
                   Type *SrcTy, Type *DstTy, int64_t CstVal, Value *DynVal,
                   size_t SmallerBitWidths) {
   if (isa<AllocaInst>(Src) && !SrcTy->isArrayTy()) {
     return Src;
   }
   auto Idxs = BitcastUtils::GetIdxsForTyFromOffset(
       DL, B, SrcTy, DstTy, CstVal, DynVal, SmallerBitWidths, Src);
   return B.CreateGEP(SrcTy, Src, Idxs, "", true);
 }

 Type *getSmallestTypeInStruct(const DataLayout &DL, StructType *Ty) {
   Type *SmallestTy = Ty;
   for (auto ElTy : Ty->elements()) {
     Type *Prev = nullptr;
     while (Prev != ElTy) {
       Prev = ElTy;
       if (auto ElSTy = dyn_cast<StructType>(ElTy)) {
         ElTy = getSmallestTypeInStruct(DL, ElSTy);
       } else {
         ElTy = BitcastUtils::GetEleType(ElTy);
       }
     }
     if (BitcastUtils::SizeInBits(DL, SmallestTy) >
         BitcastUtils::SizeInBits(DL, ElTy)) {
       SmallestTy = ElTy;
     }
   }
   return SmallestTy;
 }
 } // namespace

 llvm::PreservedAnalyses
 clspv::LowerPrivatePointerPHIPass::run(Module &M,
                                        llvm::ModuleAnalysisManager &) {
   PreservedAnalyses PA;
   for (auto &F : M) {
     runOnFunction(F);
   }
   return PA;
 }

 void clspv::LowerPrivatePointerPHIPass::runOnFunction(Function &F) {
   auto DL = F.getParent()->getDataLayout();

   bool PrivatePointerPHIOrSelect = false;
   SmallVector<AllocaInst *> worklist;
   for (auto &BB : F) {
     for (auto &I : BB) {
       if (auto alloca = dyn_cast<AllocaInst>(&I)) {
         worklist.push_back(alloca);
       } else if (auto phi = dyn_cast<PHINode>(&I)) {
         Type *Ty = phi->getType();
         if (Ty->isPointerTy() &&
             Ty->getPointerAddressSpace() == clspv::AddressSpace::Private) {
           PrivatePointerPHIOrSelect = true;
         }
       } else if (auto select = dyn_cast<SelectInst>(&I)) {
         Type *Ty = select->getType();
         if (Ty->isPointerTy() &&
             Ty->getPointerAddressSpace() == clspv::AddressSpace::Private) {
           PrivatePointerPHIOrSelect = true;
         }
       }
     }
   }

   if (!PrivatePointerPHIOrSelect) {
     return;
   }

   DenseSet<Value *> seen;
   WeakInstructions ToBeErased;
   DenseMap<PHINode *, PHINode *> PHIMap;
   DenseMap<SelectInst *, SelectInst *> SelectMap;
   DenseMap<PHINode *, AllocaInst *> PHIToBaseAlloca;
   DenseMap<SelectInst *, AllocaInst *> SelectToBaseAlloca;
   for (auto alloca : worklist) {
     auto allocaSTy = dyn_cast<StructType>(alloca->getAllocatedType());
     if (allocaSTy && BitcastUtils::IsComplexStruct(DL, allocaSTy)) {
       auto SmallestTypeInStruct = getSmallestTypeInStruct(DL, allocaSTy);
       IRBuilder<> B(alloca);
       auto nb_elem = alloca->getAllocationSizeInBits(DL).value() /
                      BitcastUtils::SizeInBits(DL, SmallestTypeInStruct);
       if (nb_elem > 1) {
         SmallestTypeInStruct = ArrayType::get(SmallestTypeInStruct, nb_elem);
       }
       auto new_alloca =
           B.CreateAlloca(SmallestTypeInStruct, alloca->getAddressSpace());
       alloca->replaceAllUsesWith(new_alloca);
       ToBeErased.push_back(alloca);
       alloca = new_alloca;
     }

     SmallVector<std::tuple<Value *, Instruction *, int64_t, Value *>> nodes;
     for (auto use : alloca->users()) {
       nodes.push_back(std::make_tuple(use, alloca, 0, nullptr));
     }
     size_t SmallerBitWidths =
         BitcastUtils::getEleTypesBitWidths(alloca->getAllocatedType(), DL)
             .back();
     while (!nodes.empty()) {
       Value *node;
       Instruction *Src;
       int64_t CstVal;
       Value *DynVal;
       std::tie(node, Src, CstVal, DynVal) = nodes.pop_back_val();
       if (seen.count(node) != 0) {
         if (auto phi = dyn_cast<PHINode>(node)) {
           auto new_phi = PHIMap[phi];
           assert(new_phi);
           assert(PHIToBaseAlloca[phi] == alloca &&
                  "PHI of pointers from different allocas not supported!");
           replacePHIIncomingValue(phi, new_phi, Src, CstVal, DynVal);
         } else if (auto select = dyn_cast<SelectInst>(node)) {
           auto new_select = SelectMap[select];
           assert(new_select);
           assert(SelectToBaseAlloca[select] == alloca &&
                  "Select of pointers from different allocas not supported!");
           IRBuilder<> B(select);
           Type *intTy = new_select->getType();
           Value *offset_val = getOffsetValue(B, intTy, CstVal, DynVal);
           if (Src == select->getTrueValue()) {
             new_select->setOperand(1, offset_val);
           }
           if (Src == select->getFalseValue()) {
             new_select->setOperand(2, offset_val);
           }
         }
         continue;
       }
       if (auto gep = dyn_cast<GetElementPtrInst>(node)) {
         IRBuilder<> B(gep);
         int64_t gep_CstVal;
         Value *gep_DynVal;
         size_t gep_SmallerBitWidths;
         BitcastUtils::ExtractOffsetFromGEP(DL, B, gep, gep_CstVal, gep_DynVal,
                                            gep_SmallerBitWidths);
         if (SmallerBitWidths > gep_SmallerBitWidths) {
           llvm_unreachable("should not be possible to have a smallerbitwidths "
                            "smaller than smallest bitwidth of src alloca");
         } else if (gep_SmallerBitWidths > SmallerBitWidths) {
           size_t coef = gep_SmallerBitWidths / SmallerBitWidths;
           gep_CstVal *= coef;
           if (gep_DynVal != nullptr) {
             gep_DynVal = BitcastUtils::CreateMul(B, coef, gep_DynVal);
           }
         }
         CstVal += gep_CstVal;
         if (DynVal == nullptr) {
           DynVal = gep_DynVal;
         } else if (gep_DynVal != nullptr) {
           DynVal = B.CreateAdd(DynVal, gep_DynVal);
         }
         ToBeErased.push_back(gep);
         for (auto use : gep->users()) {
           nodes.push_back(std::make_tuple(use, gep, CstVal, DynVal));
         }
       } else if (auto phi = dyn_cast<PHINode>(node)) {
         IRBuilder<> B(phi);
         Type *intTy = clspv::PointersAre64Bit(*(F.getParent()))
                           ? B.getInt64Ty()
                           : B.getInt32Ty();

         auto new_phi = B.CreatePHI(intTy, phi->getNumIncomingValues());
         replacePHIIncomingValue(phi, new_phi, Src, CstVal, DynVal);
         PHIMap[phi] = new_phi;
         PHIToBaseAlloca[phi] = alloca;
         ToBeErased.push_back(phi);
         for (auto &incoming : phi->incoming_values()) {
           if (isa<UndefValue>(incoming)) {
             new_phi->addIncoming(UndefValue::get(intTy),
                                  phi->getIncomingBlock(incoming));
           }
         }
         for (auto use : phi->users()) {
           nodes.push_back(std::make_tuple(use, phi, 0, new_phi));
         }
       } else if (auto select = dyn_cast<SelectInst>(node)) {
         IRBuilder<> B(select);
         Type *intTy = clspv::PointersAre64Bit(*(F.getParent()))
                           ? B.getInt64Ty()
                           : B.getInt32Ty();

         Value *true_val = select->getTrueValue();
         Value *false_val = select->getFalseValue();
         Value *new_true_val = nullptr;
         Value *new_false_val = nullptr;

         if (true_val == false_val) {
           Value *offset_val = getOffsetValue(B, intTy, CstVal, DynVal);
           new_true_val = offset_val;
           new_false_val = offset_val;
         } else {
           if (isa<ConstantPointerNull>(true_val)) {
             new_true_val = ConstantInt::get(intTy, 0);
           } else if (isa<UndefValue>(true_val)) {
             new_true_val = UndefValue::get(intTy);
           }
           if (isa<ConstantPointerNull>(false_val)) {
             new_false_val = ConstantInt::get(intTy, 0);
           } else if (isa<UndefValue>(false_val)) {
             new_false_val = UndefValue::get(intTy);
           }

           Value *offset_val = getOffsetValue(B, intTy, CstVal, DynVal);
           if (Src == true_val) {
             new_true_val = offset_val;
             if (new_false_val == nullptr) {
               new_false_val = ConstantInt::get(intTy, 0);
             }
           } else {
             assert(Src == false_val);
             new_false_val = offset_val;
             if (new_true_val == nullptr) {
               new_true_val = ConstantInt::get(intTy, 0);
             }
           }
         }

         auto new_select = cast<SelectInst>(B.CreateSelect(
             select->getCondition(), new_true_val, new_false_val));
         SelectMap[select] = new_select;
         SelectToBaseAlloca[select] = alloca;
         ToBeErased.push_back(select);
         for (auto use : select->users()) {
           nodes.push_back(std::make_tuple(use, select, 0, new_select));
         }
       } else if (auto load = dyn_cast<LoadInst>(node)) {
         IRBuilder<> B(load);
         auto gep =
             makeNewGEP(DL, B, alloca, alloca->getAllocatedType(),
                        load->getType(), CstVal, DynVal, SmallerBitWidths);
         auto new_load = B.CreateLoad(load->getType(), gep);
         load->replaceAllUsesWith(new_load);
         ToBeErased.push_back(load);
       } else if (auto store = dyn_cast<StoreInst>(node)) {
         IRBuilder<> B(store);
         auto gep =
             makeNewGEP(DL, B, alloca, alloca->getAllocatedType(),
                        store->getType(), CstVal, DynVal, SmallerBitWidths);
         B.CreateStore(store->getValueOperand(), gep);
         ToBeErased.push_back(store);
       } else if (auto ptrtoint = dyn_cast<PtrToIntInst>(node)) {
         IRBuilder<> B(ptrtoint);
         auto gep = makeNewGEP(DL, B, alloca, alloca->getAllocatedType(),
                               B.getIntNTy(SmallerBitWidths), CstVal, DynVal,
                               SmallerBitWidths);
         auto newPtrToInt = B.CreatePtrToInt(gep, ptrtoint->getDestTy());
         ptrtoint->replaceAllUsesWith(newPtrToInt);
         ToBeErased.push_back(ptrtoint);
       } else if (auto ptrtoaddr = dyn_cast<PtrToAddrInst>(node)) {
         IRBuilder<> B(ptrtoaddr);
         auto gep = makeNewGEP(DL, B, alloca, alloca->getAllocatedType(),
                               B.getIntNTy(SmallerBitWidths), CstVal, DynVal,
                               SmallerBitWidths);
         auto newPtrToAddr = B.CreatePtrToAddr(gep);
         ptrtoaddr->replaceAllUsesWith(newPtrToAddr);
         ToBeErased.push_back(ptrtoaddr);
       } else if (auto icmp = dyn_cast<ICmpInst>(node)) {
         int opId = -1;
         int otherOpIsIntToPtr = -1;
         IntToPtrInst *intToPtr = nullptr;
         for (unsigned i = 0; i < icmp->getNumOperands(); i++) {
           auto cast = dyn_cast<IntToPtrInst>(icmp->getOperand(i));
           if (icmp->getOperand(i) == Src) {
             opId = i;
           } else if (cast) {
             otherOpIsIntToPtr = i;
             intToPtr = cast;
           }
         }
         assert(opId != -1);
         IRBuilder<> B(icmp);
         if (intToPtr) {
           icmp->setOperand(otherOpIsIntToPtr, intToPtr->getOperand(0));
           Type *PtrOffTy = clspv::PointersAre64Bit(*F.getParent())
                                ? B.getInt64Ty()
                                : B.getInt32Ty();
           if (DynVal == nullptr) {
             DynVal = ConstantInt::get(PtrOffTy, CstVal);
           } else if (CstVal != 0) {
             DynVal = B.CreateAdd(DynVal, ConstantInt::get(PtrOffTy, CstVal));
           }
           icmp->setOperand(opId, DynVal);
           if (intToPtr->getNumUses() == 0) {
             ToBeErased.push_back(intToPtr);
           }
         } else {
           auto gep = makeNewGEP(DL, B, alloca, alloca->getAllocatedType(),
                                 B.getIntNTy(SmallerBitWidths), CstVal, DynVal,
                                 SmallerBitWidths);
           icmp->setOperand(opId, gep);
         }
       } else {
         llvm_unreachable("Unexpected node when traversing alloca users");
       }
       seen.insert(node);
     }
   }

   cleanDeadInstructions(ToBeErased);
 }

 void clspv::LowerPrivatePointerPHIPass::cleanDeadInstructions(
     WeakInstructions &OldInstructions) {
   // Collect all instructions that have been replaced by another one, and remove
   // them from the function. To address dependencies, use a fixed-point
   // algorithm:
   //  1. Collect the instructions that have been replaced.
   //  2. Collect among these instructions the ones which have no uses and remove
   //     them.
   //  3. Repeat step 2 until no progress is made.

   // Select instructions that were replaced by another one.
   // Ignore constants as they are not owned by the module and therefore don't
   // need to be removed.
   for (bool Progress = true; Progress;) {
     std::size_t PreviousSize = OldInstructions.size();

     // Identify instructions that are actually dead and can be removed using
     // RecursivelyDeleteTriviallyDeadInstructions.
     // Use a third buffer to capture the instructions that are still alive to
     // avoid mutating OldInstructions while iterating over it.
     WeakInstructions NextBatch;
     WeakInstructions TriviallyDeads;
     partitionInstructions(
         OldInstructions,
         [&TriviallyDeads](Instruction *DeadInstruction) {
           // Additionally, manually remove from the parent instructions with
           // possible side-effect, generally speaking, such as call or alloca
           // instructions. Those are not trivially dead.
           if (isInstructionTriviallyDead(DeadInstruction)) {
             TriviallyDeads.push_back(DeadInstruction);
           } else {
             DeadInstruction->eraseFromParent();
           }
         },
         [&NextBatch](Instruction *AliveInstruction) {
           NextBatch.push_back(AliveInstruction);
         });

     RecursivelyDeleteTriviallyDeadInstructions(TriviallyDeads);

     // Update OldInstructions for the next iteration of the fixed-point.
     OldInstructions = std::move(NextBatch);
     Progress = (OldInstructions.size() < PreviousSize);
   }

 #ifndef NDEBUG
   if (!OldInstructions.empty()) {
     dbgs() << "These values were expected to be removed:\n";
     for (auto ValueHandle : OldInstructions) {
       dbgs() << '\t' << *ValueHandle << '\n';
     }
     llvm_unreachable("Not all supposedly-dead instruction were removed!");
   }
 #endif
 }
	// Copyright 2023 The Clspv Authors. All rights reserved.
	//
	// 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 "LowerPrivatePointerPHIPass.h"
	#include "BitcastUtils.h"
	#include "Types.h"
	#include "clspv/AddressSpace.h"
	#include "llvm/ADT/DenseSet.h"
	#include "llvm/IR/Instructions.h"

	#define DEBUG_TYPE "LowerPrivatePointerPHI"

	namespace {

	using PartitionCallback = std::function<void(Instruction *)>;

	/// Partition the @p Instructions based on their liveness.
	void partitionInstructions(ArrayRef<WeakTrackingVH> Instructions,
	PartitionCallback OnDead,
	PartitionCallback OnAlive) {
	for (auto OldValueHandle : Instructions) {
	// Handle situations when the weak handle is no longer valid.
	if (!OldValueHandle.pointsToAliveValue()) {
	continue; // Nothing else to do for this handle.
	}

	auto *OldInstruction = cast<Instruction>(OldValueHandle);
	bool Dead = OldInstruction->use_empty();
	if (Dead) {
	OnDead(OldInstruction);
	} else {
	OnAlive(OldInstruction);
	}
	}
	}

	Value getOffsetValue(IRBuilder<> &B, Type intTy, int64_t CstVal,
	Value *DynVal) {
	if (DynVal == nullptr) {
	return ConstantInt::get(intTy, CstVal);
	} else if (CstVal != 0) {
	return B.CreateAdd(ConstantInt::get(intTy, CstVal), DynVal);
	}
	return DynVal;
	}

	void replacePHIIncomingValue(PHINode phi, PHINode new_phi, Instruction *Src,
	int64_t CstVal, Value *DynVal) {
	IRBuilder<> B(Src);
	Value *DynValOffset = getOffsetValue(B, new_phi->getType(), CstVal, DynVal);
	BasicBlock *BB = nullptr;
	for (auto &incoming : phi->incoming_values()) {
	if (incoming == Src) {
	BB = phi->getIncomingBlock(incoming);
	break;
	}
	}
	assert(BB);
	new_phi->addIncoming(DynValOffset, BB);
	phi->removeIncomingValue(BB, false);
	}

	Value makeNewGEP(const DataLayout &DL, IRBuilder<> &B, Instruction Src,
	Type SrcTy, Type DstTy, int64_t CstVal, Value *DynVal,
	size_t SmallerBitWidths) {
	if (isa<AllocaInst>(Src) && !SrcTy->isArrayTy()) {
	return Src;
	}
	auto Idxs = BitcastUtils::GetIdxsForTyFromOffset(
	DL, B, SrcTy, DstTy, CstVal, DynVal, SmallerBitWidths, Src);
	return B.CreateGEP(SrcTy, Src, Idxs, "", true);
	}

	Type getSmallestTypeInStruct(const DataLayout &DL, StructType Ty) {
	Type *SmallestTy = Ty;
	for (auto ElTy : Ty->elements()) {
	Type *Prev = nullptr;
	while (Prev != ElTy) {
	Prev = ElTy;
	if (auto ElSTy = dyn_cast<StructType>(ElTy)) {
	ElTy = getSmallestTypeInStruct(DL, ElSTy);
	} else {
	ElTy = BitcastUtils::GetEleType(ElTy);
	}
	}
	if (BitcastUtils::SizeInBits(DL, SmallestTy) >
	BitcastUtils::SizeInBits(DL, ElTy)) {
	SmallestTy = ElTy;
	}
	}
	return SmallestTy;
	}
	} // namespace

	llvm::PreservedAnalyses
	clspv::LowerPrivatePointerPHIPass::run(Module &M,
	llvm::ModuleAnalysisManager &) {
	PreservedAnalyses PA;
	for (auto &F : M) {
	runOnFunction(F);
	}
	return PA;
	}

	void clspv::LowerPrivatePointerPHIPass::runOnFunction(Function &F) {
	auto DL = F.getParent()->getDataLayout();

	bool PrivatePointerPHIOrSelect = false;
	SmallVector<AllocaInst *> worklist;
	for (auto &BB : F) {
	for (auto &I : BB) {
	if (auto alloca = dyn_cast<AllocaInst>(&I)) {
	worklist.push_back(alloca);
	} else if (auto phi = dyn_cast<PHINode>(&I)) {
	Type *Ty = phi->getType();
	if (Ty->isPointerTy() &&
	Ty->getPointerAddressSpace() == clspv::AddressSpace::Private) {
	PrivatePointerPHIOrSelect = true;
	}
	} else if (auto select = dyn_cast<SelectInst>(&I)) {
	Type *Ty = select->getType();
	if (Ty->isPointerTy() &&
	Ty->getPointerAddressSpace() == clspv::AddressSpace::Private) {
	PrivatePointerPHIOrSelect = true;
	}
	}
	}
	}

	if (!PrivatePointerPHIOrSelect) {
	return;
	}

	DenseSet<Value *> seen;
	WeakInstructions ToBeErased;
	DenseMap<PHINode , PHINode > PHIMap;
	DenseMap<SelectInst , SelectInst > SelectMap;
	DenseMap<PHINode , AllocaInst > PHIToBaseAlloca;
	DenseMap<SelectInst , AllocaInst > SelectToBaseAlloca;
	for (auto alloca : worklist) {
	auto allocaSTy = dyn_cast<StructType>(alloca->getAllocatedType());
	if (allocaSTy && BitcastUtils::IsComplexStruct(DL, allocaSTy)) {
	auto SmallestTypeInStruct = getSmallestTypeInStruct(DL, allocaSTy);
	IRBuilder<> B(alloca);
	auto nb_elem = alloca->getAllocationSizeInBits(DL).value() /
	BitcastUtils::SizeInBits(DL, SmallestTypeInStruct);
	if (nb_elem > 1) {
	SmallestTypeInStruct = ArrayType::get(SmallestTypeInStruct, nb_elem);
	}
	auto new_alloca =
	B.CreateAlloca(SmallestTypeInStruct, alloca->getAddressSpace());
	alloca->replaceAllUsesWith(new_alloca);
	ToBeErased.push_back(alloca);
	alloca = new_alloca;
	}

	SmallVector<std::tuple<Value , Instruction , int64_t, Value *>> nodes;
	for (auto use : alloca->users()) {
	nodes.push_back(std::make_tuple(use, alloca, 0, nullptr));
	}
	size_t SmallerBitWidths =
	BitcastUtils::getEleTypesBitWidths(alloca->getAllocatedType(), DL)
	.back();
	while (!nodes.empty()) {
	Value *node;
	Instruction *Src;
	int64_t CstVal;
	Value *DynVal;
	std::tie(node, Src, CstVal, DynVal) = nodes.pop_back_val();
	if (seen.count(node) != 0) {
	if (auto phi = dyn_cast<PHINode>(node)) {
	auto new_phi = PHIMap[phi];
	assert(new_phi);
	assert(PHIToBaseAlloca[phi] == alloca &&
	"PHI of pointers from different allocas not supported!");
	replacePHIIncomingValue(phi, new_phi, Src, CstVal, DynVal);
	} else if (auto select = dyn_cast<SelectInst>(node)) {
	auto new_select = SelectMap[select];
	assert(new_select);
	assert(SelectToBaseAlloca[select] == alloca &&
	"Select of pointers from different allocas not supported!");
	IRBuilder<> B(select);
	Type *intTy = new_select->getType();
	Value *offset_val = getOffsetValue(B, intTy, CstVal, DynVal);
	if (Src == select->getTrueValue()) {
	new_select->setOperand(1, offset_val);
	}
	if (Src == select->getFalseValue()) {
	new_select->setOperand(2, offset_val);
	}
	}
	continue;
	}
	if (auto gep = dyn_cast<GetElementPtrInst>(node)) {
	IRBuilder<> B(gep);
	int64_t gep_CstVal;
	Value *gep_DynVal;
	size_t gep_SmallerBitWidths;
	BitcastUtils::ExtractOffsetFromGEP(DL, B, gep, gep_CstVal, gep_DynVal,
	gep_SmallerBitWidths);
	if (SmallerBitWidths > gep_SmallerBitWidths) {
	llvm_unreachable("should not be possible to have a smallerbitwidths "
	"smaller than smallest bitwidth of src alloca");
	} else if (gep_SmallerBitWidths > SmallerBitWidths) {
	size_t coef = gep_SmallerBitWidths / SmallerBitWidths;
	gep_CstVal *= coef;
	if (gep_DynVal != nullptr) {
	gep_DynVal = BitcastUtils::CreateMul(B, coef, gep_DynVal);
	}
	}
	CstVal += gep_CstVal;
	if (DynVal == nullptr) {
	DynVal = gep_DynVal;
	} else if (gep_DynVal != nullptr) {
	DynVal = B.CreateAdd(DynVal, gep_DynVal);
	}
	ToBeErased.push_back(gep);
	for (auto use : gep->users()) {
	nodes.push_back(std::make_tuple(use, gep, CstVal, DynVal));
	}
	} else if (auto phi = dyn_cast<PHINode>(node)) {
	IRBuilder<> B(phi);
	Type intTy = clspv::PointersAre64Bit((F.getParent()))
	? B.getInt64Ty()
	: B.getInt32Ty();

	auto new_phi = B.CreatePHI(intTy, phi->getNumIncomingValues());
	replacePHIIncomingValue(phi, new_phi, Src, CstVal, DynVal);
	PHIMap[phi] = new_phi;
	PHIToBaseAlloca[phi] = alloca;
	ToBeErased.push_back(phi);
	for (auto &incoming : phi->incoming_values()) {
	if (isa<UndefValue>(incoming)) {
	new_phi->addIncoming(UndefValue::get(intTy),
	phi->getIncomingBlock(incoming));
	}
	}
	for (auto use : phi->users()) {
	nodes.push_back(std::make_tuple(use, phi, 0, new_phi));
	}
	} else if (auto select = dyn_cast<SelectInst>(node)) {
	IRBuilder<> B(select);
	Type intTy = clspv::PointersAre64Bit((F.getParent()))
	? B.getInt64Ty()
	: B.getInt32Ty();

	Value *true_val = select->getTrueValue();
	Value *false_val = select->getFalseValue();
	Value *new_true_val = nullptr;
	Value *new_false_val = nullptr;

	if (true_val == false_val) {
	Value *offset_val = getOffsetValue(B, intTy, CstVal, DynVal);
	new_true_val = offset_val;
	new_false_val = offset_val;
	} else {
	if (isa<ConstantPointerNull>(true_val)) {
	new_true_val = ConstantInt::get(intTy, 0);
	} else if (isa<UndefValue>(true_val)) {
	new_true_val = UndefValue::get(intTy);
	}
	if (isa<ConstantPointerNull>(false_val)) {
	new_false_val = ConstantInt::get(intTy, 0);
	} else if (isa<UndefValue>(false_val)) {
	new_false_val = UndefValue::get(intTy);
	}

	Value *offset_val = getOffsetValue(B, intTy, CstVal, DynVal);
	if (Src == true_val) {
	new_true_val = offset_val;
	if (new_false_val == nullptr) {
	new_false_val = ConstantInt::get(intTy, 0);
	}
	} else {
	assert(Src == false_val);
	new_false_val = offset_val;
	if (new_true_val == nullptr) {
	new_true_val = ConstantInt::get(intTy, 0);
	}
	}
	}

	auto new_select = cast<SelectInst>(B.CreateSelect(
	select->getCondition(), new_true_val, new_false_val));
	SelectMap[select] = new_select;
	SelectToBaseAlloca[select] = alloca;
	ToBeErased.push_back(select);
	for (auto use : select->users()) {
	nodes.push_back(std::make_tuple(use, select, 0, new_select));
	}
	} else if (auto load = dyn_cast<LoadInst>(node)) {
	IRBuilder<> B(load);
	auto gep =
	makeNewGEP(DL, B, alloca, alloca->getAllocatedType(),
	load->getType(), CstVal, DynVal, SmallerBitWidths);
	auto new_load = B.CreateLoad(load->getType(), gep);
	load->replaceAllUsesWith(new_load);
	ToBeErased.push_back(load);
	} else if (auto store = dyn_cast<StoreInst>(node)) {
	IRBuilder<> B(store);
	auto gep =
	makeNewGEP(DL, B, alloca, alloca->getAllocatedType(),
	store->getType(), CstVal, DynVal, SmallerBitWidths);
	B.CreateStore(store->getValueOperand(), gep);
	ToBeErased.push_back(store);
	} else if (auto ptrtoint = dyn_cast<PtrToIntInst>(node)) {
	IRBuilder<> B(ptrtoint);
	auto gep = makeNewGEP(DL, B, alloca, alloca->getAllocatedType(),
	B.getIntNTy(SmallerBitWidths), CstVal, DynVal,
	SmallerBitWidths);
	auto newPtrToInt = B.CreatePtrToInt(gep, ptrtoint->getDestTy());
	ptrtoint->replaceAllUsesWith(newPtrToInt);
	ToBeErased.push_back(ptrtoint);
	} else if (auto ptrtoaddr = dyn_cast<PtrToAddrInst>(node)) {
	IRBuilder<> B(ptrtoaddr);
	auto gep = makeNewGEP(DL, B, alloca, alloca->getAllocatedType(),
	B.getIntNTy(SmallerBitWidths), CstVal, DynVal,
	SmallerBitWidths);
	auto newPtrToAddr = B.CreatePtrToAddr(gep);
	ptrtoaddr->replaceAllUsesWith(newPtrToAddr);
	ToBeErased.push_back(ptrtoaddr);
	} else if (auto icmp = dyn_cast<ICmpInst>(node)) {
	int opId = -1;
	int otherOpIsIntToPtr = -1;
	IntToPtrInst *intToPtr = nullptr;
	for (unsigned i = 0; i < icmp->getNumOperands(); i++) {
	auto cast = dyn_cast<IntToPtrInst>(icmp->getOperand(i));
	if (icmp->getOperand(i) == Src) {
	opId = i;
	} else if (cast) {
	otherOpIsIntToPtr = i;
	intToPtr = cast;
	}
	}
	assert(opId != -1);
	IRBuilder<> B(icmp);
	if (intToPtr) {
	icmp->setOperand(otherOpIsIntToPtr, intToPtr->getOperand(0));
	Type PtrOffTy = clspv::PointersAre64Bit(F.getParent())
	? B.getInt64Ty()
	: B.getInt32Ty();
	if (DynVal == nullptr) {
	DynVal = ConstantInt::get(PtrOffTy, CstVal);
	} else if (CstVal != 0) {
	DynVal = B.CreateAdd(DynVal, ConstantInt::get(PtrOffTy, CstVal));
	}
	icmp->setOperand(opId, DynVal);
	if (intToPtr->getNumUses() == 0) {
	ToBeErased.push_back(intToPtr);
	}
	} else {
	auto gep = makeNewGEP(DL, B, alloca, alloca->getAllocatedType(),
	B.getIntNTy(SmallerBitWidths), CstVal, DynVal,
	SmallerBitWidths);
	icmp->setOperand(opId, gep);
	}
	} else {
	llvm_unreachable("Unexpected node when traversing alloca users");
	}
	seen.insert(node);
	}
	}

	cleanDeadInstructions(ToBeErased);
	}

	void clspv::LowerPrivatePointerPHIPass::cleanDeadInstructions(
	WeakInstructions &OldInstructions) {
	// Collect all instructions that have been replaced by another one, and remove
	// them from the function. To address dependencies, use a fixed-point
	// algorithm:
	// 1. Collect the instructions that have been replaced.
	// 2. Collect among these instructions the ones which have no uses and remove
	// them.
	// 3. Repeat step 2 until no progress is made.

	// Select instructions that were replaced by another one.
	// Ignore constants as they are not owned by the module and therefore don't
	// need to be removed.
	for (bool Progress = true; Progress;) {
	std::size_t PreviousSize = OldInstructions.size();

	// Identify instructions that are actually dead and can be removed using
	// RecursivelyDeleteTriviallyDeadInstructions.
	// Use a third buffer to capture the instructions that are still alive to
	// avoid mutating OldInstructions while iterating over it.
	WeakInstructions NextBatch;
	WeakInstructions TriviallyDeads;
	partitionInstructions(
	OldInstructions,
	[&TriviallyDeads](Instruction *DeadInstruction) {
	// Additionally, manually remove from the parent instructions with
	// possible side-effect, generally speaking, such as call or alloca
	// instructions. Those are not trivially dead.
	if (isInstructionTriviallyDead(DeadInstruction)) {
	TriviallyDeads.push_back(DeadInstruction);
	} else {
	DeadInstruction->eraseFromParent();
	}
	},
	[&NextBatch](Instruction *AliveInstruction) {
	NextBatch.push_back(AliveInstruction);
	});

	RecursivelyDeleteTriviallyDeadInstructions(TriviallyDeads);

	// Update OldInstructions for the next iteration of the fixed-point.
	OldInstructions = std::move(NextBatch);
	Progress = (OldInstructions.size() < PreviousSize);
	}

	#ifndef NDEBUG
	if (!OldInstructions.empty()) {
	dbgs() << "These values were expected to be removed:\n";
	for (auto ValueHandle : OldInstructions) {
	dbgs() << '\t' << *ValueHandle << '\n';
	}
	llvm_unreachable("Not all supposedly-dead instruction were removed!");
	}
	#endif
	}