Pre-history humans would live close to their dogs. There likely wasn't a conscious "I'll give this to Fido, and if they're good in a bit, I'll eat the rest". Instead, a dog grabbed some scraps here or there, before or after the meal. If still hungry, the dog might wander around looking for more scraps and munch on what they find.
Eventually, the food you know you can eat runs out during a hard winter or other crisis, but you see Fido munching on some things like he always does. Maybe you'll munch on those things too. Congratulations, you've acquired enough calories to make it to the next genetic lottery!
Assuming the crisis is bad enough for you to experiment but not so bad for you to eat Fido, Fido survives until the next genetic lottery too! And so we have yet another co-evolutionary moment folded into our genomes.