diff --git a/src/Reactor/Optimizer.cpp b/src/Reactor/Optimizer.cpp
index 3de6283..b4872be 100644
--- a/src/Reactor/Optimizer.cpp
+++ b/src/Reactor/Optimizer.cpp
@@ -396,7 +396,11 @@
 			bool allLoadsReplaced = true;
 		};
 
-		std::unordered_map<const Ice::InstAlloca *, LastStore> lastStoreTo;
+		// Use the (unique) index of the alloca's destination argument (i.e. the address
+		// of the allocated variable), which is of type SizeT, as the key. Note we do not
+		// use the pointer to the alloca instruction or its resulting address, to avoid
+		// undeterministic unordered_map behavior.
+		std::unordered_map<Ice::SizeT, LastStore> lastStoreTo;
 
 		for(Ice::Inst &inst : block->getInsts())
 		{
@@ -415,9 +419,11 @@
 					// a pointer which could be used for indirect stores.
 					if(getUses(address)->areOnlyLoadStore())
 					{
+						Ice::SizeT addressIdx = alloca->getDest()->getIndex();
+
 						// If there was a previous store to this address, and it was propagated
 						// to all subsequent loads, it can be eliminated.
-						if(auto entry = lastStoreTo.find(alloca); entry != lastStoreTo.end())
+						if(auto entry = lastStoreTo.find(addressIdx); entry != lastStoreTo.end())
 						{
 							Ice::Inst *previousStore = entry->second.store;
 
@@ -428,7 +434,7 @@
 							}
 						}
 
-						lastStoreTo[alloca] = { &inst };
+						lastStoreTo[addressIdx] = { &inst };
 					}
 				}
 			}
@@ -436,7 +442,8 @@
 			{
 				if(Ice::InstAlloca *alloca = allocaOf(inst.getLoadAddress()))
 				{
-					auto entry = lastStoreTo.find(alloca);
+					Ice::SizeT addressIdx = alloca->getDest()->getIndex();
+					auto entry = lastStoreTo.find(addressIdx);
 					if(entry != lastStoreTo.end())
 					{
 						const Ice::Inst *store = entry->second.store;